#include<bits/stdc++.h>
//#include "factories.h"
using namespace std;
typedef long long LL;
const int N=(int)1e6;
const int MAXLOG=19;
const LL INF=1e18+7;
vector<pair<int,int>>ke[N+2];
#define fi first
#define se second
void add_canh(int u,int v,int c){
ke[u].push_back({v,c}),ke[v].push_back({u,c});
return;
}
class Centroid{
private:
vector<int>par,sub;
vector<LL>mx;
vector<bool>del;
vector<LL>d;
vector<vector<pair<int,LL>>>pr;
public:
void init_size(int _n){
par.resize(_n+2,0);
sub.resize(_n+2,0);
del.resize(_n+2,0);
mx.resize(_n+2,INF);
d.resize(_n+2,INF);
pr.resize(_n+2);
}
void dfs(int u,int p){
sub[u]=1;
for(auto&v:ke[u]){
if (v.fi==p || del[v.fi]) continue;
dfs(v.fi,u);
sub[u]+=sub[v.fi];
}
}
void redfs(int u,int p,int root,LL dis){
pr[u].push_back({root,dis});
for(auto&v:ke[u]){
if (v.fi==p||del[v.fi]) continue;
redfs(v.fi,u,root,dis+v.second);
}
}
int Find_centroid(int u,int p,int half){
for(auto&v:ke[u]){
if (del[v.fi]||v.fi==p) continue;
if (sub[v.fi]>half) return Find_centroid(v.fi,u,half);
}
return u;
}
void build_centroid(int u,int p){
dfs(u,u);
u=Find_centroid(u,u,sub[u]/2);
redfs(u,u,u,0);
del[u]=true;
for(auto&v:ke[u]) if (del[v.fi]==0) build_centroid(v.fi,u);
}
void add(int u){
for(auto&x:pr[u]){
mx[x.first]=min(mx[x.first],x.second);
}
}
void era(int u){
for(auto&x:pr[u]){
mx[x.first]=INF;
}
}
LL Find(int u){
LL ans=INF;
for(auto&x:pr[u]){
ans=min(ans,mx[x.first]+x.second);
}
return ans;
}
};
Centroid tree;
void Init(int n,int a[],int b[],int d[]){
for(int i=0;i<n-1;++i){
++a[i],++b[i];
add_canh(a[i],b[i],d[i]);
}
tree.init_size(n);
tree.build_centroid(1,0);
return;
}
long long Query(int s,int x[],int t,int y[]){
LL ans=INF;
for(int i=0;i<s;++i) ++x[i];
for(int i=0;i<t;++i) ++y[i];
for(int i=0;i<s;++i) tree.add(x[i]);
for(int i=0;i<t;++i) ans=min(ans,tree.Find(y[i]));
for(int i=0;i<s;++i) tree.era(x[i]);
return ans;
}
