#include <bits/stdc++.h>
#define ii pair<int, long long>
using namespace std;
int up[21][500001], lg, timer = 0;
int tin[500001], tout[500001];
long long dist[500001];
vector<ii> adj[500001];
// LCA stuff
void process_lca(int a, int p){
tin[a] = timer++;
for(int i = 1; i <= lg; i++){
up[a][i] = up[up[a][i - 1]][i - 1];
}
for(auto [x, w] : adj[a]){
if(x == p) continue;
dist[x] = dist[a] + w;
process_lca(x, a);
}
tout[a] = timer++;
}
bool is_an(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
if(is_an(v, u)) return v;
for(int i = lg; i >= 0; i--){
if(!is_an(u, v)) u = up[u][i];
}
return up[u][0];
}
long long get_dist(int u, int v){
int lca_uv = lca(u, v);
return - (dist[lca_uv] << 1) + (dist[u] + dist[v]);
}
// Centroid stuff
bool blocked[500001];
int sz[500001], split_node;
int calc_subtree(int a, int p){
sz[a] = 1;
for(auto [x, w] : adj[a]){
if(x == p || blocked[x]) continue;
sz[a] += calc_subtree(x, a);
}
return sz[a];
}
bool get_split(int a, int p, int rt){
int msz = sz[rt] - sz[a];
for(auto [x, w] : adj[a]){
if(x == p || blocked[x]) continue;
msz = max(msz, sz[x]);
if(get_split(x, a, rt)) return true;
}
if(msz <= sz[rt] >> 1){
split_node = a;
return true;
}
return false;
}
int pa[500001];
void build_tree(int a, int p){
calc_subtree(a, p);
get_split(a, p, a);
pa[split_node] = p;
blocked[split_node] = true;
for(auto [x, w] : adj[split_node]){
if(blocked[x]) continue;
build_tree(x, split_node);
}
}
// Actual Problem
int bk[500001], book = 1;
long long d[500001];
void update(int u){
int tmp_u = u;
while(u != -1){
if(bk[u] < book) d[u] = get_dist(tmp_u, u);
else d[u] = min(d[u], get_dist(tmp_u, u));
bk[u] = book;
u = pa[u];
}
}
long long query(int v){
int tmp_v = v; long long ret = LLONG_MAX;
while(v != -1){
if(bk[v] == book) ret = min(ret, d[v] + get_dist(tmp_v, v));
v = pa[v];
}
return ret;
}
// Functions
void Init(int N, int* A, int* B, int* D){
lg = int(ceil(log2(N)));
for(int i = 0; i < N - 1; i++){
adj[A[i]].push_back({B[i], D[i] * 1ll});
adj[B[i]].push_back({A[i], D[i] * 1ll});
}
process_lca(0, -1);
build_tree(0, -1);
}
long long Query(int S, int* X, int T, int* Y){
long long ans = LLONG_MAX;
for(int i = 0; i < S; i++) update(X[i]);
for(int j = 0; j < T; j++) ans = min(ans, query(Y[j]));
book++;
return ans;
}
