#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, lint> pil;
typedef vector<int> Vint;
typedef vector<pil> Vpil;
const lint LNF = 2e18;
const int MAX = 5e5 + 10;
const int LG = 19;
int nu[MAX], ri[MAX], iv[MAX], dep[MAX], n;
int st[MAX][LG];
lint D[MAX];
vector<pil> G[MAX];
void dfs1(int v, int p, int cnt=0, lint sum=0){
static int now = 0;
nu[v] = ++now, ri[v] = nu[v], iv[nu[v]] = v;
dep[v] = cnt, D[v] = sum;
for(pil e:G[v]){
int x; lint c; tie(x,c) = e;
if(x==p) continue;
st[x][0] = v;
for(int i=1; i<LG; i++)
st[x][i] = st[st[x][i-1]][i-1];
dfs1(x,v,cnt+1,sum+c);
ri[v] = ri[x];
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i=0; i<n-1; i++){
int u = A[i], v = B[i], c = D[i];
G[u].push_back({v,c});
G[v].push_back({u,c});
}
dfs1(0,-1);
// for(int i=0; i<n; i++) cout<<nu[i]<<' '<<ri[i]<<'\n';
}
int lca(int u, int v){
if(dep[u]<dep[v]) swap(u,v);
for(int i=LG-1; i>=0; i--)
if(dep[u]-(1<<i)>=dep[v]) u = st[u][i];
if(u==v) return u;
for(int i=LG-1; i>=0; i--)
if(st[u][i]!=st[v][i])
u = st[u][i], v = st[v][i];
return st[u][0];
}
int C[MAX];
lint A[MAX], B[MAX];
Vint V;
int idx;
lint dfs2(){
int v = V[idx++];
lint &a = A[v], &b = B[v], res = LNF;
a = (C[v]==1 ? 0 : LNF);
b = (C[v]==2 ? 0 : LNF);
while(idx<int(V.size()) && V[idx]<=ri[iv[v]]){
int x = V[idx];
res = min(res, dfs2());
a = min(a, D[iv[x]]-D[iv[v]] + A[x]);
b = min(b, D[iv[x]]-D[iv[v]] + B[x]);
}
C[v] = 0, res = min(res, a+b);
return res;
}
lint Query(int S, int X[], int T, int Y[]) {
Vint P, Q; V.clear();
for(int i=0; i<S; i++) P.push_back(nu[X[i]]);
for(int i=0; i<T; i++) Q.push_back(nu[Y[i]]);
for(int x:P) V.push_back(x), C[x] = 1;
for(int x:Q) V.push_back(x), C[x] = 2;
sort(V.begin(), V.end());
for(int i=1, sz = int(V.size()); i<sz; i++)
V.push_back(nu[lca(iv[V[i-1]], iv[V[i]])]);
sort(V.begin(), V.end());
V.resize(unique(V.begin(), V.end()) - V.begin());
idx = 0;
return dfs2();
}
