RUNNING (PreDH 2021)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define task "running"

using namespace std;
using ld = long double;
using ll = long long;

const int N = 1e5 + 5;
const int Inf = 1e9 + 7;
int n, x, y;
int dp[N];
int u[N], v[N], c[N], par[N];
vector<int> adj[N];

void Read(){
    cin >> n >> x >> y;

    for(int i = 1; i < n; ++i){
        cin >> u[i] >> v[i] >> c[i];
        adj[u[i]].push_back(i);
        adj[v[i]].push_back(i);
    }
}

void dfs(int V) {
    for(auto z : adj[V]){
        int i = V ^ u[z] ^ v[z];
        if(i != par[V]) {
            par[i] = V;
            dp[i] = min(dp[V], c[z]);
            dfs(i);
        }
    }
}

void Solve(){
    dp[x] = Inf;
    par[x] = x;
    dfs(x);

    int ans(dp[y]);

    int k = y;
    while(par[k] != x) k = par[k];

    int maxx(0), maxy(0), resy(0), resx(0);

    for(auto z : adj[x]){
        int i = u[z] ^ x ^ v[z];
        if(i != k) maxx = max(maxx, c[z]);
        else resx = c[z];
    }

    for(auto z : adj[y]){
        int i = u[z] ^ y ^ v[z];
        if(i != par[y]) maxy = max(maxy, c[z]);
        else resy = c[z];
    }

    ans = max(ans, dp[y] + min(maxx, maxy));
    ans = max(ans, min(resx, resy + maxy));
    ans = max(ans, min(resx + maxx, resy));
    ans = max(ans, min(resx, resy));

    cout << ans;
}

int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    Read();
    Solve();
}