#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int N, Q;
// cây ban đầu
vector<pair<int,long long>> adj[MAXN];
int tin[MAXN], tout[MAXN], dep[MAXN];
long long dtr[MAXN];
int tt, lg;
vector<vector<int>> up;
// DFS build LCA, tính tin/tout và dtr[]
void dfs(int u, int p) {
tin[u] = ++tt;
up[u][0] = p;
for(int i = 1; i <= lg; i++) {
int pi = up[u][i-1];
up[u][i] = (pi < 0 ? -1 : up[pi][i-1]);
}
for(auto &e : adj[u]) {
int v = e.first;
long long w = e.second;
if (v == p) continue;
dep[v] = dep[u] + 1;
dtr[v] = dtr[u] + w;
dfs(v, u);
}
tout[u] = tt;
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u,v);
int diff = dep[u] - dep[v];
for(int i = 0; diff; i++, diff >>= 1)
if (diff & 1) u = up[u][i];
if (u == v) return u;
for(int i = lg; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
const long long INF = (long long)4e18;
// solve cho 1 query: tập A cỡ n, tập B cỡ m
long long solve(int A[], int n, int B[], int m) {
// 1) gom chung
vector<int> vs;
vs.reserve(n + m);
for(int i = 0; i < n; i++) vs.push_back(A[i]);
for(int i = 0; i < m; i++) vs.push_back(B[i]);
// 2) sort theo tin rồi thêm LCA của cặp liền kề
sort(vs.begin(), vs.end(), [&](int x,int y){ return tin[x] < tin[y]; });
int K = vs.size();
for(int i = 1; i < K; i++)
vs.push_back(lca(vs[i-1], vs[i]));
// 3) unique + sort lại
sort(vs.begin(), vs.end(), [&](int x,int y){ return tin[x] < tin[y]; });
vs.erase(unique(vs.begin(), vs.end()), vs.end());
int sz = vs.size();
// 4) đánh chỉ số
unordered_map<int,int> idx;
idx.reserve(sz*1.3);
for(int i = 0; i < sz; i++) idx[vs[i]] = i;
// 5) build virtual-tree
vector<vector<pair<int,long long>>> vt(sz);
vector<int> st;
st.reserve(sz);
for(int i = 0; i < sz; i++){
int u = vs[i], idu = i;
while(!st.empty()) {
int top = st.back();
int v = vs[top];
if (tin[v] <= tin[u] && tout[u] <= tout[v]) break;
st.pop_back();
}
if (!st.empty()) {
int top = st.back();
int v = vs[top];
long long w = dtr[u] - dtr[v];
vt[top].emplace_back(idu, w);
vt[idu].emplace_back(top, w);
}
st.push_back(idu);
}
// 6) multi-source init
vector<long long> da(sz, INF), db(sz, INF);
for(int i = 0; i < n; i++) da[idx[A[i]]] = 0;
for(int i = 0; i < m; i++) db[idx[B[i]]] = 0;
long long ans = INF;
// post-order
function<void(int,int)> dfs1 = [&](int u, int p){
for(auto &e: vt[u]) {
int v = e.first;
long long w = e.second;
if (v == p) continue;
dfs1(v, u);
da[u] = min(da[u], da[v] + w);
db[u] = min(db[u], db[v] + w);
}
ans = min(ans, da[u] + db[u]);
};
// pre-order
function<void(int,int)> dfs2 = [&](int u, int p){
for(auto &e: vt[u]) {
int v = e.first;
long long w = e.second;
if (v == p) continue;
da[v] = min(da[v], da[u] + w);
db[v] = min(db[v], db[u] + w);
ans = min(ans, da[v] + db[v]);
dfs2(v, u);
}
};
int root = st.front();
dfs1(root, -1);
dfs2(root, -1);
return ans;
}
// được gọi 1 lần
void Init(int N, int U[], int V[], int D[]) {
::N = N;
for(int i = 0; i < N; i++) adj[i].clear();
for(int i = 0; i < N-1; i++) {
adj[U[i]].emplace_back(V[i], (long long)D[i]);
adj[V[i]].emplace_back(U[i], (long long)D[i]);
}
tt = 0;
dep[0] = dtr[0] = 0;
lg = floor(log2(N));
up.assign(N, vector<int>(lg+1, -1));
dfs(0, -1);
}
// được gọi Q lần
long long Query(int S, int X[], int T, int Y[]) {
return solve(X, S, Y, T);
}
