#include<bits/stdc++.h>
//#include "factories.h"
using namespace std;
#define ll long long
#define fi first
#define se second
#define pb push_back
typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;
const ll N = 5e5 + 5, oo = 1e18 + 7, mod = 1e9 + 7;
ll n;
vector<pair<ll, ll>> Adj[N];
ll d1[N], d2[N];
ll anc[N][20];
void dfs(ll u, ll p){
for(auto it : Adj[u]){
ll v = it.fi, w = it.se;
if(v == p) continue;
d1[v] = d1[u] + 1;
d2[v] = d2[u] + w;
anc[v][0] = u;
//dist[v][0] = w;
dfs(v, u);
}
}
void prep(){
for(ll i = 1; i <= 19; i++){
for(ll j = 1; j <= n; j++){
anc[j][i] = anc[anc[j][i - 1]][i - 1];
//dist[j][i] = dist[j][i - 1] + dist[anc[j][i - 1]][i - 1];
}
}
}
ll lca(ll x, ll y){
if(d1[x] > d1[y]) swap(x, y);
for(ll i = 19; i >= 0; i--){
if((d1[x] + (1LL << i)) <= d1[y]) y = anc[y][i];
}
if(x == y) return x;
for(ll i = 19; i >= 0; i--){
if(anc[x][i] != anc[y][i]){
x = anc[x][i], y = anc[y][i];
}
}
return anc[x][0];
}
ll dist(ll x, ll y){
return d2[x] + d2[y] - 2 * d2[lca(x, y)];
}
ll cnt;
ll pos[N], l[N], r[N];
ll arr[N];
void pre_dfs(ll u, ll p){
cnt++;
pos[u] = l[u] = cnt;
arr[cnt] = u;
for(auto it : Adj[u]){
ll v = it.fi;
if(v == p) continue;
pre_dfs(v, u);
}
r[u] = cnt;
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(ll i = 0; i < (n - 1); i++){
Adj[A[i] + 1].pb({B[i] + 1, D[i]});
Adj[B[i] + 1].pb({A[i] + 1, D[i]});
}
pre_dfs(1, 1);
dfs(1, 1);
prep();
}
bool cmp(ll a, ll b){
return l[a] < l[b];
}
ll type[N];
pair<ll, ll> mini[N];
vector<pair<ll, ll>> Adj2[N];
void dfs3(ll u){
mini[u] = {oo, oo};
if(type[u] == 1) mini[u].fi = 0;
if(type[u] == 2) mini[u].se = 0;
for(auto it : Adj2[u]){
ll v = it.fi, w = it.se;
dfs3(v);
mini[u].fi = min(mini[u].fi, mini[v].fi + w);
mini[u].se = min(mini[u].se, mini[v].se + w);
}
}
ll Query(int S, int X[], int T, int Y[]){
//return 0;
vector<ll> vc;
for(ll i = 0; i < S; i++){
vc.pb(X[i] + 1);
type[X[i] + 1] = 1;
}
for(ll i = 0; i < T; i++){
vc.pb(Y[i] + 1);
type[Y[i] + 1] = 2;
}
// for(ll i = 0; i < T; i++) vc.pb(Y[i] + 1);
sort(vc.begin(), vc.end(), cmp);
vector<ll> nodes;
for(auto it : vc) nodes.pb(it);
for(ll i = 0; (i + 1) < vc.size(); i++){
ll temp = lca(vc[i], vc[i + 1]);
nodes.pb(temp);
}
sort(nodes.begin(), nodes.end(), cmp);
nodes.resize(unique(nodes.begin(), nodes.end()) - nodes.begin());
set<iii> se;
ll root;
for(auto it : nodes){
set<iii>::iterator it2 = se.lower_bound({{r[it], -oo}, -oo});
if(it2 != se.end()){
// cout << it << " " << (*it2).se << "\n";
Adj2[((*it2).se)].pb({it, dist(it, (*it2).se)});
}
else root = it;
se.insert({{r[it], r[it] - l[it] + 1}, it});
}
//return 0;
dfs3(root);
ll answer = oo;
for(auto it : nodes) answer = min(answer, mini[it].fi + mini[it].se);
for(auto it : nodes) Adj2[it].clear();
//sort(nodes.begin(), nodes.end(), greater<ii>());
for(auto it : nodes) type[it] = 0;
return answer;
}
