#include <vector>
#include <climits>
#include <iostream>
using namespace std;
#define pb push_back
#define mp make_pair
#define MAXN 500001
#define LOGN 25
typedef long long ll;
typedef pair<int,int> pii;
int num_nodes,num_q,sz[MAXN],lvl[MAXN],par[MAXN],upd[MAXN],qcnt,A[MAXN],B[MAXN],D[MAXN],cur_lvl;
ll small[MAXN],dis[MAXN][LOGN];
pii ret;
bool done[MAXN];
vector<pii> tconnections[MAXN];
int getSz(int node, int prev, ll dd){
sz[node] = 1;
dis[node][cur_lvl] = dd;
for(pii check:tconnections[node]){
if(check.first == prev || done[check.first]) continue;
sz[node]+=getSz(check.first,node,dd+check.second);
}
return sz[node];
}
int centroid(int node, int prev, int psz){
sz[node] = 1;
int mxsz = 0;
for(pii check:tconnections[node]){
if(check.first == prev || done[check.first]) continue;
centroid(check.first,node,psz);
mxsz = max(mxsz,sz[check.first]);
sz[node]+=sz[check.first];
}
mxsz = max(mxsz, psz-sz[node]);
if(mxsz < ret.first) ret = mp(mxsz, node);
return ret.second;
}
void getTree(int node, int prev, int mx, int lv){
cur_lvl = lv;
ret = mp(INT_MAX,-1);
node = centroid(node,-1,mx);
par[node] = prev, lvl[node] = lv, done[node] = true;
// getSz(node,-1,0);
for(pii check:tconnections[node]){
if(check.first == prev || done[check.first]) continue;
getTree(check.first,node,sz[check.first],lv+1);
}
}
void Init(int N, int A[MAXN], int B[MAXN], int D[MAXN]){
for(int i=0; i<N-1; i++){
int a = A[i], b = B[i], dis = D[i];
tconnections[a].pb(mp(b,dis));
tconnections[b].pb(mp(a,dis));
}
getTree(0,-1,num_nodes,0);
}
ll Query(int s1, int X[MAXN], int s2, int Y[MAXN]){
++qcnt;
for(int i=0; i<s1; i++){
int current = X[i];
while(current != -1){
if(upd[current] == qcnt) small[current] = small[current]<dis[X[i]][lvl[current]]?small[current]:dis[X[i]][lvl[current]];
else small[current] = dis[X[i]][lvl[current]], upd[current] = qcnt;
current = par[current];
}
}
ll best = LONG_MAX;
for(int i=0; i<s2; i++){
int current = Y[i];
while(current != -1){
if(upd[current] == qcnt) best = best<dis[Y[i]][lvl[current]]+small[current]?best:dis[Y[i]][lvl[current]]+small[current];
current = par[current];
}
}
return best;
}
