#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define lc (i << 1)
#define rc (i << 1 | 1)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 5e5 + 5, LN = 17, MOD = 1e9 + 7, INF = 0x3f3f3f3f, BSZ = 320;
vector<pii> g[MN];
int sz[MN], par[MN], dep[MN], qid[MN], id = 1;
ll dis[20][MN], dp[MN];
bool vis[MN];
int get_sz(int u, int p) {
sz[u] = 1;
for (pii e : g[u]) if (e.first != p && !vis[e.first])
sz[u] += get_sz(e.first, u);
return sz[u];
}
int centroid(int u, int p, int s) {
for (pii e : g[u]) if (e.first != p && !vis[e.first] && sz[e.first] > s / 2)
return centroid(e.first, u, s);
return u;
}
void dfs(int u, int p, ll d, int lvl) {
dis[lvl][u] = d;
for (pii e : g[u]) if (e.first != p && !vis[e.first])
dfs(e.first, u, d + e.second, lvl);
}
void go(int u, int p, int lvl) {
int c = centroid(u, -1, get_sz(u, -1));
dep[c] = lvl;
par[c] = p;
dfs(c, -1, 0, lvl);
vis[c] = true;
for (pii e : g[c])
if (!vis[e.first])
go(e.first, c, lvl + 1);
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N; i++) {
int u = A[i], v = B[i], w = D[i];
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
go(0, -1, 0);
}
ll Query(int S, int X[], int T, int Y[]) {
ll ret = LLONG_MIN;
for (int i = 0; i < S; i++) {
int cur = X[i];
while (cur != -1) {
if (qid[cur] != id) dp[cur] = dis[dep[cur]][X[i]], qid[cur] = id;
else dp[cur] = min(dp[cur], dis[dep[cur]][X[i]]);
cur = par[cur];
}
}
for (int i = 0; i < T; i++) {
int cur = Y[i];
while (cur != -1) {
if (qid[cur] == id) ret = min(ret, dp[cur] + dis[dep[cur]][Y[i]]);
cur = par[cur];
}
}
id++;
return ret;
}
