#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
using pp=pair<int,int>;
using ll=long long;
const int maxn = int(5e5) + 10;
const ll inf = (1ll<<60);
int n, q;
vector<pp> e[maxn];
int tin[maxn], tout[maxn], nt;
int par[20][maxn];
int dep[maxn];
ll dd[maxn];
void dfs(int x) {
tin[x] = ++nt;
for (auto tmp:e[x]) {
int y, d; tie(y, d) = tmp;
if (y == par[0][x]) continue;
par[0][y] = x;
dep[y] = dep[x]+1;
dd[y] = dd[x] + d;
dfs(y);
}
tout[x] = nt;
}
int lca(int a, int b) {
if (dep[a] > dep[b]) swap(a, b);
for (int df=dep[b]-dep[a], i=18; 0<=i; --i)
if (1&(df>>i)) b = par[i][b];
if (a == b) return a;
for (int i=18; 0<=i; --i) if (par[i][a] != par[i][b])
a = par[i][a], b = par[i][b];
return par[0][a];
}
vector<int> vx, vy;
vector<int> va;
bitset<maxn> isx;
bitset<maxn> isy;
vector<pair<int,ll>> te[maxn];
ll dx[maxn], dy[maxn];
pair<ll,ll> tdfs(int x, pair<ll,ll> pd) {
if (isx[x]) pd.first = 0;
else if (isy[x]) pd.second = 0;
ll cx = inf, cy = inf;
for (auto tmp : te[x]) {
int y; ll d; tie(y, d) = tmp;
ll ccx, ccy; tie(ccx, ccy) = tdfs(y, {pd.first+d, pd.second+d});
cx = min(cx, ccx+d);
cy = min(cy, ccy+d);
}
dx[x] = min(cx, pd.first);
dy[x] = min(cy, pd.second);
if (isx[x]) cx = 0;
else if (isy[x]) cy = 0;
return {cx, cy};
}
void Init(int n, int A[], int B[], int D[]) {
for (int i=0; i<n-1; ++i) {
e[A[i]+1].emplace_back(B[i]+1, D[i]);
e[B[i]+1].emplace_back(A[i]+1, D[i]);
}
dfs(1);
for (int i=1; i<=18; ++i) for (int j=1; j<=n; ++j) {
par[i][j] = par[i-1][par[i-1][j]];
}
}
ll Query(int nx, int X[], int ny, int Y[]) {
vx.clear(); vx.insert(vx.end(), X, X+nx); for (int &x:vx) ++x;
vy.clear(); vy.insert(vy.end(), Y, Y+ny); for (int &y:vy) ++y;
va.resize(nx + ny);
copy(vx.begin(), vx.end(), va.begin());
copy(vy.begin(), vy.end(), va.begin()+nx);
sort(va.begin(), va.end(), [&](const int& a, const int& b) {
return tin[a] < tin[b];
});
for (int i=0; i+1<nx+ny; ++i) {
int a = va[i], b = va[i+1], l = lca(a, b);
if (l != a && l != b) va.push_back(l);
}
sort(va.begin(), va.end(), [&](const int& a, const int& b) {
return tin[a] < tin[b];
});
va.erase(unique(va.begin(), va.end()), va.end());
static vector<int> stk; stk.clear();
for (int x : va) {
while (!stk.empty()) {
int p = stk.back();
if (tin[p] <= tin[x] && tin[x] <= tout[p]) break;
stk.pop_back();
}
if (!stk.empty()) {
int p = stk.back();
te[p].emplace_back(x, dd[x]-dd[p]);
}
stk.push_back(x);
}
for (int x : vx) isx.set(x);
for (int y : vy) isy.set(y);
tdfs(va[0], {inf, inf});
ll ans = inf;
for (int a : va) ans = min(ans, dx[a]+dy[a]);
for (int x : va) te[x].clear();
for (int x : vx) isx.reset(x);
for (int y : vy) isy.reset(y);
return ans;
}
