#include <bits/stdc++.h>
using namespace std;
#define sz(v) ((int)((v).size()))
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define coord_comp(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define v_index(v, x) (lower_bound(all(v),x)-(v).begin())
typedef pair<int,int> pp;
typedef long long ll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T1,typename T2>
void read(pair<T1,T2>& p){ read(p.first); read(p.second); }
template<typename T,typename... Args>
void read(T&a,Args&...b){ read(a); read(b...); }
typedef pair<int,ll> pil;
vector<pil> edge[500010];
vector<int> comp[500010];
int par[20][500010];
ll depth[500010];
int d2 [500010];
int n,q;
int tin[500010];
int nt;
void dfs(int x){
tin[x]=nt++;
for(auto& yp:edge[x]){
int y=yp.first; ll d=yp.second;
if(par[0][x] != y){
par[0][y] = x;
depth[y] = depth[x] + d;
d2[y] = d2[x]+1;
dfs(y);
}
}
}
int lca(int a,int b){
if(d2[a]>d2[b]) swap(a,b);
int df=d2[b]-d2[a];
for(int i=18; 0<=i; --i) if(1&(df>>i)) b=par[i][b];
for(int i=18; 0<=i; --i) if(par[i][a]!=par[i][b])
a=par[i][a], b=par[i][b];
if(a!=b) a=par[0][a];
return a;
}
void sparse(){
par[0][0] = -1;
for(int i=1; i<=18; ++i) for(int j=0; j<n; ++j){
int t=par[i-1][j];
if(t==-1) par[i][j]=-1;
else par[i][j]=par[i-1][t];
}
}
bool isPar(int a,int b){
if(d2[a]>d2[b]) return false;
int df=d2[b]-d2[a];
for(int i=18; 0<=i; --i){
if(1&(df>>i)) b=par[i][b];
}
return a==b;
}
ll dA[500010];
ll dB[500010];
vector<int> hist;
void compress(vector<int>& pts){
stack<int> stk;
hist.clear();
for(int p : pts){
comp[p].clear();
while(stk.size() && !isPar(stk.top(), p))
hist.pb(stk.top()), stk.pop();
if(stk.size()) comp[stk.top()].pb(p);
stk.push(p);
}
while(stk.size()) hist.pb(stk.top()), stk.pop();
}
ll inf=(1LL<<60);
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i=0; i<n-1; ++i){
int a=A[i],b=B[i],d=D[i];
edge[a].pb({b,d}); edge[b].pb({a,d});
}
dfs(0); sparse();
}
long long Query(int A, int X[], int B, int Y[]) {
vector<int> pa(X, X+A), pb(Y, Y+B), pts;
for(int x:pa) pts.pb(x);
for(int x:pb) pts.pb(x);
auto timecomp = [&](const int& a, const int& b){
return tin[a]<tin[b];
};
sort(all(pts), timecomp);
int sz=A+B;
for(int i=1; i<sz; ++i) pts.pb(lca(pts[i-1], pts[i]));
sort(all(pts), timecomp);
pts.erase(unique(all(pts)), pts.end());
compress(pts);
for(int x:pts) dA[x]=dB[x]=inf;
for(int x:pa) dA[x]=0;
for(int x:pb) dB[x]=0;
ll ans=inf;
for(int x:hist){
for(int y:comp[x]){
dA[x] = min(dA[x], dA[y]+depth[y]-depth[x]);
dB[x] = min(dB[x], dB[y]+depth[y]-depth[x]);
}
ans=min(ans, dA[x]+dB[x]);
}
return ans;
}
