#include <bits/stdc++.h>
#define MAX 505000
typedef std::pair<int,int> pii;
std::vector<pii> con[MAX];
bool existe[MAX];
int dfs(int pos,int prev){
int size=1;
for(auto&x:con[pos]){
if(x.first==prev||existe[x.first])continue;
size+=dfs(x.first,pos);
}
return size;
}
int centroide=0;
int find(int pos,int prev,int sz){
int size=1;
int max=0;
for(auto&x:con[pos]){
if(x.first==prev||existe[x.first])continue;
int b = find(x.first,pos,sz);
max=std::max(max,b);
size+=b;
}
max=std::max(max,sz-size);
if(max<=sz/2)centroide=pos;
return size;
}
int conna[MAX];
int nivel[MAX];
long long dists[MAX][25];
void explora(int pos,int prev,int lvl,long long dist){
dists[pos][lvl]=dist;
for(auto&x:con[pos]){
if(x.first==prev||existe[x.first])continue;
explora(x.first,pos,lvl,dist+x.second);
}
}
void Decompor(int x,int lvl=0,int prev=-1){
int tam=dfs(x,-1);
find(x,-1,tam);
int c = centroide;
explora(c,-1,lvl,0);
nivel[c]=lvl;
existe[c]=true;
conna[c]=prev;
for(auto&x:con[c]){
if(existe[x.first])continue;
Decompor(x.first,lvl+1,c);
}
}
long long tabela[MAX];
void Add(int p){
int o=p;
int nv = nivel[p];
while(p!=-1){
tabela[p]=std::min(tabela[p],dists[o][nv]);
--nv;
p=conna[p];
}
}
void Zera(int p){
while(p!=-1){
tabela[p]=1LL<<50LL;
p=conna[p];
}
}
long long Check(int p){
int o=p;
int nv = nivel[p];
long long ans=1LL<<50LL;
while(p!=-1){
ans=std::min(ans,tabela[p]+dists[o][nv]);
--nv;
p=conna[p];
}
return ans;
}
void Init(int N,int A[],int B[],int D[]){
for(int i=0;i!=N-1;++i){
int a = A[i],b=B[i],c=D[i];
con[a].push_back({b,c});
con[b].push_back({a,c});
}
Decompor(0);
for(auto&x:tabela)x=1LL<<50LL;
}
long long Query(int S,int X[],int T,int Y[]){
for(int i=0;i!=S;++i){
Add(X[i]);
}
long long ans=1LL<<50LL;
for(int i=0;i!=T;++i){
ans=std::min(ans,Check(Y[i]));
}
for(int i=0;i!=S;++i){
Zera(X[i]);
}
return ans;
}
