#include<bits/stdc++.h>
#define pb push_back
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int N=5e5+5;
vector<pair<int,ll>>g[N];
int sz[N]{0};
bool vis[N]{0};
ll dp[N]{0};
vector<pair<int,ll>>ancestor[N];
int getsize(int u,int p){
sz[u]=1;
for(auto v:g[u]){
if(vis[v.f]||v.f==p)continue;
sz[u]+=getsize(v.f,u);
}return sz[u];
}
int get_centroid(int u,int p,int n){
for(auto v:g[u]){
if(vis[v.f]||v.f==p)continue;
if(sz[v.f]*2>n)return get_centroid(v.f,u,n);
}return u;
}
void gen_dist(int u,int p,int centroid,ll cur){
for(auto v:g[u]){
if(vis[v.f]||v.f==p)continue;
gen_dist(v.f,u,centroid,cur+v.s);
}ancestor[u].pb({centroid,cur});
}
void play(int u=0){
int centroid=get_centroid(u,u,getsize(u,u));
for(auto v:g[centroid]){
if(vis[v.f])continue;
gen_dist(v.f,centroid,centroid,v.s);
}vis[centroid]=1;
for(auto v:g[centroid]){
if(vis[v.f])continue;
play(v.f);
}
}
void upd(int u){
for(auto v:ancestor[u]){
dp[v.f]=min(dp[v.f],v.s);
}dp[u]=0;
}
ll qry(int u){
ll ans=dp[u];
for(auto v:ancestor[u]){
ans=min(ans,v.s+dp[v.f]);
}return ans;
}
void Init(int N,int A[],int B[],int D[]){
for(int i=0;i<N;i++)dp[i]=1e16;
for(int i=0;i<N-1;i++){
g[A[i]].pb({B[i],D[i]});g[B[i]].pb({A[i],D[i]});
}play();
}
long long Query(int S,int X[],int T,int Y[]){
for(int i=0;i<S;i++){
upd(X[i]);
}
ll ans=1e16;
for(int i=0;i<T;i++){
ans=min(ans,qry(Y[i]));
}
for(int i=0;i<S;i++){
dp[X[i]]=1e16;
for(auto it : ancestor[X[i]])dp[it.f]=1e16;
}
return ans;
}
