#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
const int maxN = 5e5 + 7;
int n, level[maxN], st[maxN], ed[maxN], cnt = 0, now = 0, sz = 0, euler[2 * maxN], lg[2 * maxN], ft[maxN];
long long depth[maxN], ans;
pair <int, int> cur[4 * maxN], par[20][2 * maxN];
vector < pair <int, int> > edge[maxN];
void dfs(int u, int p){
st[u] = ++cnt;
euler[++now] = u;
ft[u] = now;
for(pair <int, int> to : edge[u]){
int v = to.fi, w = to.se;
if(v == p) continue;
level[v] = level[u] + 1;
depth[v] = depth[u] + w;
dfs(v, u);
euler[++now] = u;
}
ed[u] = cnt;
}
pair <int, int> get(int l, int r){
int add = lg[r - l + 1];
return min(par[add][l], par[add][r - (1 << add) + 1]);
}
int lca(int u, int v){
if(ft[u] > ft[v]) swap(u, v);
return get(ft[u], ft[v]).se;
}
bool cmp(pair <int, int> x, pair <int, int> y){
return st[x.fi] < st[y.fi];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0; i < n - 1; i++){
A[i]++, B[i]++;
edge[A[i]].pb(mp(B[i], D[i]));
edge[B[i]].pb(mp(A[i], D[i]));
}
level[1] = 1;
dfs(1, 1);
for(int i = 1; i <= now; i++) par[0][i] = mp(level[euler[i]], euler[i]);
for(int i = 2; i <= 2 * n; i++) lg[i] = lg[i >> 1] + 1;
for(int i = 1; i < 20; i++){
for(int j = 1; j + (1 << i) - 1 <= now; j++){
par[i][j] = min(par[i - 1][j], par[i - 1][j + (1 << (i - 1))]);
}
}
st[n + 1] = 1e9;
}
pair <long long, long long> solve(){
int u = cur[cnt].fi;
long long A = 1e18, B = 1e18;
if(cur[cnt].se == 0) A = min(A, depth[u]);
if(cur[cnt].se == 1) B = min(B, depth[u]);
cnt++;
if(cnt > sz) return mp(A, B);
while(cur[cnt].fi == u){
if(cur[cnt].se == 0) A = min(A, depth[u]);
if(cur[cnt].se == 1) B = min(B, depth[u]);
cnt++;
}
while(ed[u] >= st[cur[cnt].fi]){
pair <long long, long long> tmp = solve();
A = min(A, tmp.fi), B = min(B, tmp.se);
}
ans = min(ans, A + B - 2LL * depth[u]);
return mp(A, B);
}
long long Query(int S, int X[], int T, int Y[]) {
ans = 1e18;
sz = 0;
for(int i = 0; i < S; i++) cur[++sz] = mp(X[i] + 1, 0);
for(int i = 0; i < T; i++) cur[++sz] = mp(Y[i] + 1, 1);
sort(cur + 1, cur + 1 + sz, cmp);
int sv = sz;
for(int i = 1; i < sv; i++) cur[++sz] = mp(lca(cur[i].fi, cur[i + 1].fi), 2);
cur[++sz] = mp(n + 1, 0);
sort(cur + 1, cur + 1 + sz, cmp);
//for(int i = 1; i <= sz; i++) cout << cur[i].fi << endl;
cnt = 1;
solve();
return ans;
}
