#include <bits/stdc++.h>
#define ii pair<int, long long>
using namespace std;
int sz[500005], lvl[500005], pa[500005];
bool blocked[500005];
vector<ii> adj[500005];
long long dist[21][500005];
// Centroid
void dfs(int a, int p){
sz[a] = 1;
for(auto [x, w]: adj[a]){
if(blocked[x] || x == p) continue;
dfs(x, a);
sz[a] += sz[x];
}
}
void dfs_dis(int a, int p, int lv){
for(auto [x, w] : adj[a]){
if(x == p || blocked[x]) continue;
dist[lv][x] = dist[lv][a] + w;
dfs_dis(x, a, lv);
}
}
void dec(int a, int p){
dfs(a, a);
int cur = a, prev = -1;
while(true){
int mx = -1, ch;
for(auto [x, w] : adj[cur]){
if(blocked[x] || x == prev) continue;
if(sz[x] > mx){
mx = sz[x];
ch = x;
}
}
if(mx * 2 > sz[a]){
prev = cur;
cur = ch;
}
else break;
}
lvl[cur] = p == -1 ? 0 : lvl[p] + 1;
dfs_dis(cur, cur, lvl[cur]);
blocked[cur] = true;
pa[cur] = p;
for(auto [x, w] : adj[cur]) if(!blocked[x]) dec(x, cur);
}
long long val[500005];
void Init(int N, int A[], int B[], int D[]){
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});
}
dec(0, -1);
for(int i = 0; i < N; i++) val[i] = 1e15;
}
void upd(int u){
int old_u = u;
for(; u != -1; u = pa[u]){
val[u] = min(val[u], dist[lvl[u]][old_u]);
}
}
long long query(int u){
long long res = 1e15;
int old_u = u;
for(; u != -1; u = pa[u]){
res = min(res, val[u] + dist[lvl[u]][old_u]);
}
return res;
}
void reset(int u){
for(; u != -1; u = pa[u]) val[u] = 1e15;
}
long long Query(int S, int X[], int T, int Y[]) {
long long res = 1e15;
for(int i = 0; i < S; i++) upd(X[i]);
for(int i = 0; i < T; i++) res = min(res, query(Y[i]));
for(int i = 0; i < S; i++) reset(X[i]);
return res;
}
