#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ertunt return
#define rall(x) x.rbegin(),x.rend()
using namespace std;
ll lg = 20;
ll n;
vector<ll>sz(500005);
vector<ll>dead(500005);
vector<ll>parC(500005,-1);
vector<vector<pair<ll,ll>>>adj(500005);
vector<ll>best(500005,1e15);
vector<ll>def(500005,0);
vector<ll>h(500005);
vector<vector<ll>>anc(500005);
vector<vector<ll>>dista(500005);
void dfs(ll x,ll p,ll d){
def[x] = d;
h[x] = (p==-1 ? 0 : h[p]+1);
for(auto [y,w] : adj[x]){
if(y!=p) dfs(y,x,d+w);
}
}
ll dfs_size(ll x,ll p){
sz[x] = 1;
for(auto [y,w] : adj[x]){
if(y != p && !dead[y]){
sz[x] += dfs_size(y,x);
}
}
return sz[x];
}
ll dfs_centroid(ll x,ll p,ll compsize){
for(auto [y,w] : adj[x]){
if(y != p && !dead[y]){
if(sz[y] > compsize/2) return dfs_centroid(y,x,compsize);
}
}
return x;
}
void dfs_dist(ll u,ll p,ll c,ll d){
anc[u].pb(c);
dista[u].pb(d);
for(auto [v,w]: adj[u]){
if(v!=p && !dead[v]) dfs_dist(v,u,c,d+w);
}
}
void build(ll x,ll p){
ll compsize = dfs_size(x,-1);
ll c = dfs_centroid(x,-1,compsize);
parC[c] = p;
dead[c] = 1;
dfs_dist(c,-1,c,0);
for(auto [y,w] : adj[c]){
if(!dead[y]) build(y,c);
}
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(ll i = 0; i < n; i++){
adj[i].clear();
dead[i] = 0;
parC[i] = -1;
best[i] = 1e15;
anc[i].clear();
dista[i].clear();
}
for(ll i = 0; i < n-1; i++){
adj[A[i]].pb({B[i],D[i]});
adj[B[i]].pb({A[i],D[i]});
}
dfs(0,-1,0);
build(0,-1);
}
void upd(ll u, vector<ll>& touched){
for(ll i=0;i<anc[u].size();i++){
ll c = anc[u][i];
ll d = dista[u][i];
if(best[c]==1e15) touched.pb(c);
best[c] = min(best[c],d);
}
}
ll Query(int S, int A[], int T, int B[]){
vector<ll> touched;
for(int i=0;i<S;i++) upd(A[i],touched);
ll ans = 1e18;
for(int i=0;i<T;i++){
for(ll j=0;j<anc[B[i]].size();j++){
ll c = anc[B[i]][j];
ll d = dista[B[i]][j];
ans = min(ans,best[c]+d);
}
}
for(auto x:touched) best[x] = 1e15;
return ans;
}
