#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>adj[500005];
long long vis[500005],sz[500005],pa[500005],dis[20][500005];
int lv[500005];
int n;
long long mn[500005];
long long inf=1e15;
int dfssz(int u,int p){
sz[u]=1;
for(auto [x,d]:adj[u])if(!vis[x]&&x!=p){
sz[u]+=dfssz(x,u);
}
return sz[u];
}
int centroid(int u,int p,int rsz){
for(auto [x,d]:adj[u])if(!vis[x]&&x!=p&&sz[x]*2>=rsz)return centroid(x,u,rsz);
return u;
}
void dfs(int u,int p,long long d,int l){
dis[l][u]=d;
for(auto [x,c]:adj[u])if(!vis[x]&&x!=p){
dfs(x,u,d+c,l);
}
}
void decom(int u,int p){
u=centroid(u,-1,dfssz(u,-1));
lv[u]=(p==-1?0:lv[p]+1);
vis[u]=1;
pa[u]=p;
dfs(u,-1,0,lv[u]);
for(auto [x,d]:adj[u]){
if(vis[x])continue;
decom(x,u);
}
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(int i=0;i<n;i++){
adj[A[i]].push_back({B[i],D[i]});
adj[B[i]].push_back({A[i],D[i]});
}
decom(0,-1);
for(int i=0;i<n;i++)mn[i]=inf;
}
void upd(int x){
int og=x;
for(;x!=-1;x=pa[x])mn[x]=min(mn[x],dis[lv[x]][og]);
}
void del(int x){
int og=x;
for(;x!=-1;x=pa[x])mn[x]=inf;
}
long long fans(int x){
int og=x;
long long ans=inf;
//cerr<<"fans:"<<x<<"\n";
for(;x!=-1;x=pa[x]){
ans=min(ans,mn[x]+dis[lv[x]][og]);
//cerr<<x<<" "<<mn[x]<<"\n";
}
return ans;
}
long long Query(int S, int X[], int T, int Y[]) {
long long ans=LLONG_MAX;
for(int i=0;i<S;i++)upd(X[i]);
for(int i=0;i<T;i++)ans=min(ans,fans(Y[i]));
for(int i=0;i<S;i++)del(X[i]);
return ans;
}
