# include <iostream>
# include <vector>
# include <map>
using namespace std;
# include "factories.h"
//# include "grader.cpp"
const long long INF=1e18;
const int MAX=5e5+11;
int n;
vector<pair<int,long long>> adj[MAX];
int sz[MAX];
bool kill[MAX];
void dfs_sz(int curr, int par)
{
sz[curr]=1;
for(pair<int,long long> nxt: adj[curr])
{
if(nxt.first==par or kill[nxt.first]) continue;
dfs_sz(nxt.first,curr);
sz[curr]+=sz[nxt.first];
}
}
int get_centroid(int curr, int par, int N)
{
for(pair<int,long long> nxt: adj[curr])
{
if(nxt.first==par or kill[nxt.first]) continue;
if(sz[nxt.first]*2>N) return get_centroid(nxt.first,curr,N);
}
return curr;
}
vector<pair<int,long long>> anc[MAX];
void dfs(int curr, int par, int cen, long long dep)
{
anc[curr].push_back({cen,dep});
for(pair<int,long long> nxt: adj[curr])
{
if(nxt.first==par or kill[nxt.first]) continue;
dfs(nxt.first,curr,cen,dep+nxt.second);
}
}
void cd(int curr)
{
dfs_sz(curr,-1);
curr=get_centroid(curr,-1,sz[curr]);
dfs(curr,-1,curr,0);
kill[curr]=1;
for(pair<int,long long> nxt: adj[curr])
{
if(kill[nxt.first]) continue;
cd(nxt.first);
}
}
void Init(int N, int A[], int B[], int D[])
{
n=N;
for(int i=0;i<N-1;i++)
{
int u=A[i],v=B[i],w=D[i];
adj[u].push_back({v,w});
adj[v].push_back({u,w});
}
cd(0);
}
map<long long,int> s[MAX];
void change(int curr, bool add)
{
for(pair<int,long long> P: anc[curr])
{
int cen=P.first;
long long w=P.second;
if(add) s[cen][w]++;
else
{
s[cen][w]--;
if(s[cen][w]==0) s[cen].erase(w);
}
}
}
long long query(int curr)
{
long long ans=INF;
for(pair<int, long long> P: anc[curr])
{
int cen=P.first;
long long w=P.second;
if((int)s[cen].size()>0) ans=min(ans,w+s[cen].begin()->first);
}
return ans;
}
long long Query(int S, int X[], int T, int Y[])
{
for(int i=0;i<S;i++) change(X[i],1);
long long ans=INF;
for(int i=0;i<T;i++) ans=min(ans,query(Y[i]));
for(int i=0;i<S;i++) change(X[i],0);
return ans;
}
/*
7 1
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
3 2
0 1 3
4 6
*/
