#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;
#include "factories.h"
int n;
vector<P>E[600000];
vector<ll>d[600000];
bool used[600000];
int sz[600000];
int par[600000];
ll dist[600000];
int szdfs(int v,int p){
sz[v]=1;
for(auto u:E[v]){
if(u.second==p||used[u.second])continue;
sz[v]+=szdfs(u.second,v);
}
return sz[v];
}
int search_centroid(int v,int p,int s){
int ret=-1;
int m=0;
for(auto u:E[v]){
if(u.second==p||used[u.second])continue;
int res=search_centroid(u.second,v,s);
if(res!=-1)ret=res;
m=max(m,sz[u.second]);
}
if(max(m,s-sz[v])<=n/2){
ret=v;
}
return ret;
}
void dfs(int v,int p,ll w){
d[v].push_back(w);
for(auto u:E[v]){
if(u.second==p||used[u.second])continue;
dfs(u.second,v,w+u.first);
}
}
void build(int v){
szdfs(v,-1);
int s=search_centroid(v,-1,sz[v]);
used[s]=true;
dfs(s,-1,0);
for(auto u:E[s]){
if(used[u.second])continue;
par[u.second]=s;
build(u.second);
}
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
rep(i,n-1){
E[A[i]].push_back(P(D[i],B[i]));
E[B[i]].push_back(P(D[i],A[i]));
}
build(0);
memset(dist,0x3f,sizeof(dist));
}
long long Query(int S, int X[], int T, int Y[]) {
rep(i,S){
int v=X[i];
for(int j=d[X[i]].size()-1;j>=0;j--){
dist[v]=min(dist[v],d[X[i]][j]);
if(j)v=par[v];
}
}
ll ans=INF;
rep(i,T){
int v=Y[i];
for(int j=d[Y[i]].size()-1;j>=0;j--){
ans=min(ans,dist[v]+d[Y[i]][j]);
if(j)v=par[v];
}
}
rep(i,S){
int v=X[i];
for(int j=d[X[i]].size()-1;j>=0;j--){
dist[v]=INF;
if(j)v=par[v];
}
}
return ans;
}
