#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
const int MN = 5e5+3, LOG = 19, MOD = 1e9+7;
mt19937_64 rnd = mt19937_64(chrono::steady_clock::now().time_since_epoch().count());
int op[MN][LOG], od[MN], sz[MN], p[MN]; bool done[MN]; ll down[MN], up[MN], oup[MN][LOG];
vector<pii> adj[MN];
void prep (int cur) {
for (pii i : adj[cur]) if (i.first != op[cur][0]) {
op[i.first][0] = cur; oup[i.first][0] = i.second; od[i.first] = od[cur] + 1;
for (int j = 1; j < LOG; j++)
if (op[i.first][j-1])
op[i.first][j] = op[op[i.first][j-1]][j-1], oup[i.first][j] = oup[i.first][j-1] + oup[op[i.first][j-1]][j-1];
prep(i.first);
}
}
ll dist (int a, int b) {
if (od[a] < od[b]) swap(a,b);
ll ret = 0;
for (int i = LOG-1; i >= 0; i--)
if (op[a][i] && od[op[a][i]] >= od[b])
ret += oup[a][i], a = op[a][i];
if (a == b) return ret;
for (int i = LOG-1; i >= 0; i--)
if (op[a][i] && op[b][i] && op[a][i] != op[b][i])
ret += oup[a][i] + oup[b][i], a = op[a][i], b = op[b][i];
return ret + oup[a][0] + oup[b][0];
}
int dfs (int cur, int par = -1) {
sz[cur] = 1;
for (pii i : adj[cur]) if (!done[i.first] && i.first != par) {
sz[cur] += dfs(i.first,cur);
}
return sz[cur];
}
int findcent (int cur, int tot, int par = -1) {
for (pii i : adj[cur]) {
if (i.first != par && !done[i.first] && sz[i.first] > (tot>>1))
return findcent(i.first,tot,cur);
}
return cur;
}
void maketree (int cur, int lst = 0) {
dfs(cur);
int cent = findcent(cur,sz[cur]);
done[cent] = 1;
p[cent] = lst;
for (pii i : adj[cent]) if (!done[i.first]) maketree(i.first,cent);
}
void Init (int n, int *a, int *b, int *d) {
for (int i = 0; i < n-1; i++) {
adj[++a[i]].emplace_back(++b[i],d[i]);
adj[b[i]].emplace_back(a[i],d[i]);
}
prep(1);
maketree(1);
memset(down,0x3f,sizeof down);
}
ll Query (int s, int *x, int t, int *y) {
ll ret = LLONG_MAX;
for (int i = 0; i < s; i++) {
int st = ++x[i], cur = st;
while (cur) {
down[cur] = min(down[cur],dist(cur,st));
cur = p[cur];
}
}
for (int i = 0; i < t; i++) {
int st = ++y[i], cur = st;
while (cur) {
ret = min(ret,dist(st,cur)+down[cur]);
cur = p[cur];
}
}
assert(ret != LLONG_MAX);
for (int i = 0; i < s; i++) {
int cur = x[i];
while(cur) {
down[cur] = 1e18;
cur = p[cur];
}
}
return ret;
}
