#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
const int MOD = 1000 * 1000 * 1000 + 7;
vector<pair<int, ll>> adj[500001];
int par[500001], level[500001], sz[500001];
ll dist[500001][22], ans[500001];
bool rem[500001];
/// CENTROID DECOMPOSITION :
int dfs_size(int v, int p) {
sz[v] = 1;
for(auto u: adj[v]) {
if(u.ff == p || rem[u.ff]) continue;
sz[v] += dfs_size(u.ff, v);
}
return sz[v];
}
int centroid(int v, int p, int N) {
for(auto u : adj[v]) {
if(u.ff == p || rem[u.ff]) continue;
if(sz[u.ff] >= N / 2)
return centroid(u.ff, v, N);
}
return v;
}
void dfs(int v, int p, int L) {
for(auto u : adj[v]) {
if(u.ff == p || rem[u.ff]) continue;
dist[u.ff][L] = dist[v][L] + u.ss;
dfs(u.ff, v, L);
}
}
void build(int v, int p) {
int N = dfs_size(v, p);
int C = centroid(v, p, N);
level[C] = (p != -1 ? level[p] + 1 : 0);
par[C] = p; dfs(C, C, level[C]); rem[C] = 1;
for(auto u : adj[C]) {
if(rem[u.ff]) continue;
build(u.ff, C);
}
}
void Init(int N, int A[], int B[], int D[]) {
for(int l = 0; l < N - 1; l++) {
int U = A[l], V = B[l], W = D[l];
adj[U].pb({V, W}), adj[V].pb({U, W});
}
for(int l = 0; l < N; l++) ans[l] = 1e18 + 7;
build(0, -1);
}
void update(int U) {
int V = U;
for(; V != -1; V = par[V])
ans[V] = min(ans[V], dist[U][level[V]]);
}
ll query(int U) {
int V = U; ll res = 1e18 + 7;
for(; V != -1; V = par[V])
res = min(res, ans[V] + dist[U][level[V]]);
return res;
}
void reset(int U) {
for(; U != -1; U = par[U])
ans[U] = 1e18 + 7;
}
long long Query(int S, int X[], int T, int Y[]) {
ll res = 1e18 + 7;
for(int l = 0; l < S; l++) update(X[l]);
for(int l = 0; l < T; l++)
res = min(res, query(Y[l]));
for(int l = 0; l < S; l++) reset(X[l]);
return res;
}
