#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
#define int long long
#define fi first
#define se second
const int N = 5e5 + 5;
int sz[N], bl[N], mnd[N];
vector<pair<int, int>> adj[N], anc[N];
bool c[N];
void dfs_sz(int u, int p) {
sz[u] = 1;
for (auto& [v, w] : adj[u]) {
if (v == p || c[v]) continue;
dfs_sz(v, u);
sz[u] += sz[v];
}
}
int dfs_cent(int u, int p, int tot) {
int res = -1, mx = 0;
for (auto& [v, w] : adj[u]) {
if (v == p || c[v]) continue;
res = max(res, dfs_cent(v, u, tot));
mx = max(mx, sz[v]);
}
mx = max(mx, tot - sz[u]);
if (mx <= tot / 2) res = max(res, u);
return res;
}
void redfs(int cent, int u, int p, int dist) {
anc[u].push_back({cent, dist});
for (auto& [v, w] : adj[u]) {
if (v == p || c[v]) continue;
redfs(cent, v, u, dist + w);
}
}
void decomp(int u) {
dfs_sz(u, -1);
int cent = dfs_cent(u, -1, sz[u]);
c[cent] = 1;
redfs(cent, cent, -1, 0);
for (auto& [v, w] : adj[cent]) {
if (c[v]) continue;
decomp(v);
}
}
const int inf = 1e18;
#define Int int32_t
void Init(Int n, Int a[], Int b[], Int d[]) {
for (int i = 0; i < n - 1; i++) {
a[i]++, b[i]++;
adj[a[i]].push_back({b[i], d[i]});
adj[b[i]].push_back({a[i], d[i]});
}
decomp(1);
for (int i = 1; i <= n; i++) mnd[i] = inf;
}
int Query(Int s, Int x[], Int t, Int y[]) {
for (int i = 0; i < s; i++) {
x[i]++;
for (auto& [u, dist] : anc[x[i]]) mnd[u] = min(mnd[u], dist);
}
int ans = inf;
for (int i = 0; i < t; i++) {
y[i]++;
for (auto& [u, dist] : anc[y[i]]) ans = min(ans, mnd[u] + dist);
}
for (int i = 0; i < s; i++) {
for (auto& [u, dist] : anc[x[i]]) mnd[u] = inf;
}
return ans;
}
