#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sp << ' ' <<
#define nl << '\n'
#define v e.first
#define w e.second
#include "factories.h"
const int MAXN = 5e5;
const ll INF = 1e18;
vector<vector<pair<int, ll>>> g(MAXN);
vector<vector<ll>> dist(20, vector<ll> (MAXN));
vector<int> s(MAXN), depth(MAXN), parent(MAXN);
vector<bool> r(MAXN);
vector<ll> ans(MAXN, INF);
int calcSize(int u, int p){
s[u] = 1;
for(auto &e : g[u]) if(v != p and !r[v]) s[u] += calcSize(v, u);
return s[u];
}
void calcDist(int u, int p, ll currDist, int lvl){
dist[lvl][u] = currDist;
for(auto &e : g[u]) if(v != p and !r[v]) calcDist(v, u, currDist + w, lvl);
}
int find(int u, int p, int treeSize){
for(auto &e : g[u]) if(v != p and !r[v] and s[v] > treeSize/2) return find(v, u, treeSize);
return u;
}
int decompose(int u, int lvl){
int c = find(u, u, calcSize(u, u));
calcDist(c, c, 0, lvl);
r[c] = true, depth[c] = lvl++;
for(auto &e : g[c]) if(!r[v]) parent[decompose(v, lvl)] = c;
return c;
}
void build(int u, int source){
ans[u] = min(ans[u], dist[depth[u]][source]);
if(depth[u]) build(parent[u], source);
}
void reset(int u){
ans[u] = INF;
if(depth[u]) reset(parent[u]);
}
ll get(int u, int source){
if(!depth[u]) return ans[u] + dist[depth[u]][source];
else return min(ans[u] + dist[depth[u]][source], get(parent[u], source));
}
void Init(int N, int A[], int B[], int D[]){
for(int i=0; i<N-1; ++i){
g[A[i]].emplace_back(B[i], D[i]);
g[B[i]].emplace_back(A[i], D[i]);
}
decompose(0, 0);
}
ll Query(int S, int X[], int T, int Y[]){
for(int i=0; i<S; ++i) build(X[i], X[i]);
ll res = INF;
for(int i=0; i<T; ++i) res = min(res, get(Y[i], Y[i]));
for(int i=0; i<S; ++i) reset(X[i]);
return res;
}
