#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
const int M=5e5+10;
bool rem[M];
vector<pair<int,long long>> adj[M],dc[M];
long long dist[M];
int upd[M];
//dist to centroid {centroid,dist}
int sz[M],t=1;
void findsz(int u,int p=-1){
sz[u]=1;
for(auto [v,w]:adj[u]){
if(v==p || rem[v]) continue;
findsz(v,u);
sz[u]+=sz[v];
}
}
void dfs(int u,int p,int ed,long long d=0){
dc[u].push_back({ed,d});
for(auto [v,w]:adj[u]){
if(v==p || rem[v]) continue;
dfs(v,u,ed,d+w);
}
}
int cen(int u,int treesz,int p=-1){
for(auto [v,w]:adj[u]){
if(v==p || rem[v]) continue;
if(sz[v]*2>treesz) return cen(v,treesz,u);
}
return u;
}
void decom(int u){
findsz(u);
int c=cen(u,sz[u]);
dfs(c,-1,c);
//now parent centroid
rem[c]=true;
for(auto [v,w]:adj[c]){
if(rem[v]) continue;
decom(v);
}
}
void Init(int N, int A[], int B[], int D[]) {
for(int i=0;i<N-1;i++){
adj[A[i]].push_back({B[i],D[i]});
adj[B[i]].push_back({A[i],D[i]});
}
decom(0);
/*for(int i=0;i<N;i++){
cout<<i <<"\n";
for(auto [cen,d]:dc[i]){
cout<<cen <<" " <<d <<"\n";
}
}*/
}
long long Query(int S, int X[], int T, int Y[]){
for(int i=0;i<S;i++){
int u=X[i];
for(auto [cen,d]:dc[u]){
if(upd[cen]!=t){
upd[cen]=t;
dist[cen]=d;
}
else{
dist[cen]=min(dist[cen],d);
}
}
}
long long ans=LLONG_MAX;
for(int i=0;i<T;i++){
int u=Y[i];
for(auto [cen,d]:dc[u]){
if(upd[cen]!=t) continue;
ans=min(ans,dist[cen]+d);
}
}
t++;
return ans;
}
