#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
char lvl[500001];
int par[500001], sz[500001];
ll dist[500001][20], ans[500001];
bool done[500001];
vector<pii> adj[500001];
void dfs(int u, int p, int curlvl, ll d) {
sz[u] = 1;
dist[u][curlvl] = d;
for (pii v : adj[u]) {
if (v.first != p && !done[v.first]) {
dfs(v.first, u, curlvl, d + v.second);
sz[u] += sz[v.first];
}
}
}
int centre(int u, int p, int tot) {
for (pii v : adj[u]) {
if (v.first != p && !done[v.first] && sz[v.first]<<1 > tot) {
return centre(v.first, u, tot);
}
}
return u;
}
void decomp(int i, int p, int curlvl, int tot) {
dfs(i, -1, curlvl, 0);
int c = centre(i, -1, tot);
dfs(c, -1, curlvl, 0);
done[c] = true;
lvl[c] = curlvl;
par[c] = p;
for (pii v : adj[c]) {
if (v.first != p && !done[v.first]) {
decomp(v.first, c, curlvl+1, sz[v.first]);
}
}
}
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]});
adj[B[i]].push_back({A[i], D[i]});
}
for (int i = 0; i < 500000; i++)
ans[i] = 0x3f3f3f3f3f3f3f3f;
decomp(0, -1, 0, N);
}
long long Query(int S, int X[], int T, int Y[]) {
ll mn = 0x3f3f3f3f3f3f3f3f;
for (int i = 0; i < S; i++) {
int cur = X[i];
while(cur != -1) {
ans[cur] = min(ans[cur], dist[X[i]][lvl[cur]]);
cur = par[cur];
}
}
for (int i = 0; i < T; i++) {
int cur = Y[i];
while(cur != -1) {
mn = min(mn, dist[Y[i]][lvl[cur]] + ans[cur]);
cur = par[cur];
}
}
for (int i = 0; i < S; i++) {
int cur = X[i];
while(cur != -1) {
ans[cur] = 0x3f3f3f3f3f3f3f3f;
cur = par[cur];
}
}
return mn;
}
