#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 pil = pair<int,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
const int MN = 5e5+3, LOG = 20, MOD = 1e9+7;
mt19937_64 rnd = mt19937_64(chrono::steady_clock::now().time_since_epoch().count());
int sz[MN], p[MN], st[MN], tt=0; bool done[MN]; ll push[MN], down[MN], up[MN], sp[MN<<1][LOG];
vector<pii> adj[MN];vector<pil> go[MN];
void prep (int cur, int par = -1) {
sp[st[cur] = ++tt][0] = push[cur];
for (pii i : adj[cur]) if (i.first != par) {
push[i.first] = push[cur] + i.second;
prep(i.first,cur);
sp[++tt][0] = push[cur];
}
}
void initlca () {
for (int j = 1; j < LOG; j++)
for (int i = 1; i <= tt-(1<<j)+1; i++)
sp[i][j] = min(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
ll dist (int a, int b) {
if (a == b) return 0;
if (st[a] > st[b]) swap(a,b);
int lg = 31 - __builtin_clz(st[b]-st[a]+1);
return push[a] + push[b] - min(sp[st[a]][lg],sp[st[b]-(1<<lg)+1][lg])*2;
}
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);
initlca();
for (int i = 1; i <= n; i++) {
int cur = i;
while (cur) {
go[i].emplace_back(cur,dist(i,cur));
cur = p[cur];
}
}
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++) {
for (auto &pp : go[++x[i]])
if (pp.second < down[pp.first])
down[pp.first] = pp.second;
}
for (int i = 0; i < t; i++) {
for (auto &pp : go[++y[i]])
ret = min(ret,pp.second + down[pp.first]);
}
for (int i = 0; i < s; i++) {
for (auto &pp : go[x[i]])
down[pp.first] = 1e18;
}
return ret;
}
