//Power Of Ninja Go
#include <bits/stdc++.h>
#ifdef atom
#include "grader.cpp"
#else
#include "factories.h"
#endif
using namespace std;
typedef long long ll; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector< ii > vii;
#define X first
#define Y second
#define pb push_back
#define mp make_pair
const int maxn = 5e5+5;
vii adj[maxn];
int dp[22][maxn];
int h[maxn];
ll sweep[maxn];
int cnt[maxn];
bool use[maxn];
int tim = 1;
int zil[maxn];
ll red[4*maxn], blue[4*maxn];
int n;
ll query(ll *st, int i, int j, int p = 1, int L = 1, int R = n)
{
if(i> R || j< L) return 4e18;
if(i<= L && R<= j) return st[p];
ll x = query(st, i, j, 2*p, L, (L+R)/2);
ll y = query(st, i, j, 2*p+1, (L+R)/2+1, R);
return min(x, y);
}
void build(ll *st, vector<pair<int, int> > &vec, int p = 1, int L = 1, int R = n)
{
if(L == R)
{
st[p] = sweep[vec[L].Y];
return;
}
build(st, vec, 2*p, L, (L+R)/2);
build(st, vec, 2*p+1, (L+R)/2+1, R);
st[p] = min(st[2*p], st[2*p+1]);
}
void trv(int u, int p)
{
cnt[u] = 1;
zil[u] = tim;
tim++;
for(auto &edge : adj[u])
{
int v = edge.X, w = edge.Y;
if(v != p)
{
h[v] = h[u]+1;
dp[0][v] = u;
sweep[v] = sweep[u]+w;
trv(v, u);
cnt[u] += cnt[v];
}
}
}
bool cmp(int u, int v)
{
return zil[u]< zil[v];
}
int LCA(int u, int v)
{
if(h[u]< h[v]) swap(u, v);
//printf("%d %d\n", u, v);
for(int i = 19; i>= 0; i--)
{
int x = dp[i][u];
if(h[x]>= h[v]) u = x;
}
if(u == v) return u;
//printf("%d\n", h[7]);
//printf("now %d %d\n", u, v);
for(int i = 29; i>= 0; i--)
{
int x = dp[i][u], y = dp[i][v];
if(x == y) continue;
u = x; v = y;
}
return dp[0][u];
}
ll dist(int u, int v)
{
int x = LCA(u, v);
return sweep[u]+sweep[v]-2LL*sweep[x];
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for(int i = 0; i< N-1; i++)
{
int u, v; u = A[i]+1; v = B[i]+1;
int w = D[i];
adj[u].pb(ii(v, w));
adj[v].pb(ii(u, w));
}
h[1] = 1; trv(1, 0);
for(int i = 1; i<= 19; i++)
for(int j = 1; j<= N; j++)
dp[i][j] = dp[i-1][dp[i-1][j]];
}
long long Query(int S, int X[], int T, int Y[])
{
vector<int> all;
vector< ii > b, r;
b.pb(ii(-1e9, 0));
r.pb(ii(-1e9, 0));
for(int i = 0; i< S; i++) X[i]++;
for(int i = 0; i< T; i++) Y[i]++;
for(int i = 0; i< S; i++) all.pb(X[i]), r.pb(mp(zil[X[i]], X[i]));
for(int i = 0; i< T; i++) all.pb(Y[i]), b.pb(mp(zil[Y[i]], Y[i]));
sort(r.begin(), r.end()); sort(b.begin(), b.end());
build(red, r, 1, 1, S); build(blue, b, 1, 1, T);
sort(all.begin(), all.end(), cmp);
//for(auto x : all) printf("%d ", x);
//printf("\n");
vector<int> matt; matt = all;
for(int i = 1; i< (int) all.size(); i++)
{
int x = LCA(all[i], all[i-1]);
if(x == all[i] or x == all[i-1]) continue;
matt.pb(x);
}
ll best = 4e18;
for(auto &top : matt)
{
int lend = zil[top], rend = zil[top]+cnt[top]-1;
int x1 = lower_bound(r.begin(), r.end(), mp(lend, -1))-r.begin();
int y1 = upper_bound(r.begin(), r.end(), mp(rend, 500001))-r.begin()-1;
int x2 = lower_bound(b.begin(), b.end(), mp(lend, -1))-b.begin();
int y2 = upper_bound(b.begin(), b.end(), mp(rend, 500001))-b.begin()-1;
ll bestred = query(red, x1, y1, 1, 1, S);
ll bestblue = query(blue, x2, y2, 1, 1, T);
best = min(best, bestred+bestblue-2*sweep[top]);
}
return best;
}
