// In the Name of Allah
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O2,unroll-loops")
#pragma GCC optimize ("Ofast")
#pragma gcc optimize("Ofast")
#pragma optimize(Ofast)
typedef long long ll;
const ll N = 5e5 + 12, inf = 1e18 + 12;
vector<pair<int, int>> g[N];
int sz[N], cpar[N], q, n;
ll val[N];
unordered_map<int, ll> cdis[N];
bool mrk[N];
void dfs(int u, int par = -1) {
sz[u] = 1;
for (auto i: g[u])
if (i.first != par && !mrk[i.first]) {
dfs(i.first, u);
sz[u] += sz[i.first];
}
}
int find_centroid(int u, int c, int par = -1) {
for (auto i: g[u])
if (!mrk[i.first] && i.first != par && sz[i.first] > (c - 1) / 2)
return find_centroid(i.first, c, u);
return u;
}
void fill_cdis(int u, int cent, ll c = 0, int par = -1) {
cdis[cent][u] = c;
for (auto i: g[u])
if (!mrk[i.first] && i.first != par)
fill_cdis(i.first, cent, c + i.second, u);
}
void decompose(int u, int par = -1) {
dfs(u);
u = find_centroid(u, sz[u]);
fill_cdis(u, u);
cpar[u] = par;
mrk[u] = true;
for (auto i: g[u])
if (!mrk[i.first])
decompose(i.first, u);
}
void add(int u, int v) {
if (u == -1)
return;
val[u] = min(val[u], cdis[u][v]);
add(cpar[u], v);
}
ll ask(int u, int v) {
if (u == -1)
return inf;
ll tmp = cdis[u][v];
return min(ask(cpar[u], v), tmp + val[u]);
}
void rem(int u) {
val[u] = inf;
if (cpar[u] != -1)
rem(cpar[u]);
}
void Init(int c, int a[], int b[], int d[]) {
n = c;
for (int i = 0; i < n - 1; i++) {
g[a[i]].push_back({b[i], d[i]});
g[b[i]].push_back({a[i], d[i]});
}
decompose(0);
fill(val, val + n, inf);
}
ll Query(int s, int x[], int t, int y[]) {
for (int i = 0; i < s; i++)
add(x[i], x[i]);
ll res = inf;
for (int i = 0; i < t; i++)
res = min(res, ask(y[i], y[i]));
for (int i = 0; i < s; i++)
rem(x[i]);
return res;
}
