#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fir first
#define sec second
#define pb push_back
const ll maxn=5e5;
ll n;
vector<ii>adj[maxn+2];
ll sub[maxn+2];
bool vis[maxn+2];
void dfs(ll cur,ll par){
sub[cur]=1;
for(auto [x,di] : adj[cur]){
if(x==par)continue;
if(vis[x]){
sub[x]=0; continue;
}
dfs(x,cur);
sub[cur]+=sub[x];
}
}
ll centro(ll cur,ll par,ll sz){
for(auto [x,di] : adj[cur]){
if(x==par || vis[x])continue;
if(sub[x]>=sz/2){
return centro(x,cur,sz);
}
}
return cur;
}
vector<ii>anc[maxn+2];
void comp(ll cur,ll par,ll root,ll tot){
anc[cur].pb({tot,root});
for(auto [x,di] : adj[cur]){
if(x==par || vis[x])continue;
comp(x,cur,root,tot+di);
}
}
void solve(ll cur){
dfs(cur,0);
ll root=centro(cur,0,sub[cur]);
comp(root,0,root,0);
vis[root]=true;
for(auto [x,di] : adj[root]){
if(vis[x])continue;
solve(x);
}
}
ll dkt[maxn+2];
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(int q=0;q<n-1;q++){
adj[A[q]].pb({B[q],D[q]});
adj[B[q]].pb({A[q],D[q]});
}
solve(1);
for(int q=0;q<N;q++)dkt[q]=1e18;
}
void update(ll idx){
for(auto [tot,root] : anc[idx]){
//cout<<idx<<" "<<tot<<" "<<root<<endl;
dkt[root]=min(dkt[root],tot);
}
}
void reset(ll idx){
for(auto [tot,root] : anc[idx]){
dkt[root]=1e18;
}
}
ll query(ll idx){
ll ans=1e18;
for(auto [tot,root] : anc[idx]){
//cout<<idx<<" "<<tot<<" "<<root<<" "<<dkt[root]<<endl;
ans=min(ans,tot+dkt[root]);
}
return ans;
}
ll Query(int S, int X[], int T, int Y[]) {
for(int q=0;q<S;q++){
update(X[q]);
}
ll ans=1e18;
for(int q=0;q<T;q++){
ans=min(ans,query(Y[q]));
}
for(int q=0;q<S;q++){
reset(X[q]);
}
return ans;
}
// signed main(){
// int N,qu;
// cin>>N>>qu;
// int A[N],B[N],D[N];
// for(int q=0;q<N-1;q++){
// cin>>A[q]>>B[q]>>D[q];
// }
// Init(N,A,B,D);
// for(int q=0;q<N;q++){
// cout<<vis[q]<<" ";
// }
// cout<<endl;
// while(qu--){
// int S,T;
// cin>>S>>T;
// int X[S],Y[T];
// for(int q=0;q<S;q++)cin>>X[q];
// for(int q=0;q<T;q++)cin>>Y[q];
// cout<<Query(S,X,T,Y)<<endl;
// }
// }
