#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)
#define ff first
#define ss second
const int N = 5e5 + 5;
const ll inf = 1e17 + 100;
int n, p[N], sz[N], LVL[N];
ll h[N][20];
bool vis[N];
multiset <ll> s[N];
vector <ii> adj[N];
vector <int> ra;
int size(int u, int f){
sz[u] = 1;
for(auto p: adj[u]){
if(p.ff != f and !vis[p.ff]) sz[u] += size(p.ff, u);
}
return sz[u];
}
int get_centroid(int u, int f, int curr_size){
for(auto p: adj[u]) if(p.ff != f and !vis[p.ff] and sz[p.ff]*2 > curr_size)
return get_centroid(p.ff, u, curr_size);
return u;
}
void dfs(int u, int f, int lvl){
for(auto p: adj[u]){
ll v = p.ff, w = p.ss;
if(vis[v] or v == f) continue;
h[v][lvl] = h[u][lvl] + w;
dfs(v, u, lvl);
}
}
void descompose(int u, int f, int lvl){
int cen = get_centroid(u, f, size(u, f));
vis[cen] = 1;
LVL[cen] = ++lvl;
p[cen] = f, h[cen][lvl] = 0;
dfs(cen, f, lvl);
for(auto p: adj[cen]) if(!vis[p.ff]) descompose(p.ff, cen, lvl);
}
void Init(int ni, int a[], int b[], int d[]){
n = ni;
f(i,0,n-1){
adj[a[i]].push_back({b[i], d[i]});
adj[b[i]].push_back({a[i], d[i]});
}
descompose(0, -1, 0);
}
void paint_red(int u){
int aux = u;
while(u != -1){
ra.push_back(u);
s[u].insert(h[aux][LVL[u]]);
u = p[u];
}
}
void paint_white(int u){
int aux = u;
while(u != -1){
auto it = s[u].find(h[aux][LVL[u]]);
s[u].erase(it);
u = p[u];
}
}
ll get(int u){
ll ans = inf, aux = u;
while(u != -1){
if(!s[u].empty()){
ans = min(ans, h[aux][LVL[u]] + *s[u].begin());
}
u = p[u];
}
return ans;
}
ll Query(int S, int X[], int T, int Y[]){
ra.clear();
f(i,0,S) paint_red(X[i]);
ll ans = inf;
f(i,0,T) ans = min(ans, get(Y[i]));
for(int x: ra) s[x].clear();
return ans;
}
