#include<bits/stdc++.h>
using namespace std;
const int maxn=500005;
int tin[maxn],tout[maxn];
int dep[maxn],dtr[maxn];
vector<pair<int,int>> adj[maxn];
int tt,lg;
vector<vector<int>> up;
long long inf=LLONG_MAX/4,ans;
void dfs(int u,int par) {
tin[u]=++tt;
up[u][0]=par;
for(int i=1;i<=lg;++i) {
if(up[u][i-1]!=-1) {
up[u][i]=up[up[u][i-1]][i-1];
}
else break;
}
for(pair<int,int> p:adj[u]) {
int v=p.first,w=p.second;
if(v==par) 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 k=dep[u]-dep[v];
for(int i=0;k>0;++i) {
if(k&1) {
u=up[u][i];
}
k>>=1;
}
if(u==v) return u;
for(int i=lg;i>=0;--i) {
if(up[u][i]!=-1&&up[v][i]!=-1&&up[u][i]!=up[v][i]) {
u=up[u][i];
v=up[v][i];
}
}
return up[u][0];
}
long long solve(int a[], int n, int b[], int m) {
// 1) gom tất cả nút của A và B vào cùng 1 vector
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 và thêm LCA của các cặp liền kề
sort(vs.begin(), vs.end(), [&](int u, int v){
return tin[u] < tin[v];
});
int K = vs.size();
for(int i = 1; i < K; i++){
int u = vs[i-1], v = vs[i];
vs.push_back(lca(u, v));
}
// 3) unique lại và sort theo tin nữa
sort(vs.begin(), vs.end(), [&](int u, int v){
return tin[u] < tin[v];
});
vs.erase(unique(vs.begin(), vs.end()), vs.end());
int sz = vs.size();
// 4) đánh số lại (node -> idx)
unordered_map<int,int> idx;
idx.reserve(sz * 1.3);
vector<vector<pair<int,int>>> vt(sz);
for(int i = 0; i < sz; i++){
idx[vs[i]] = i;
vt[i].clear();
}
// 5) build virtual tree bằng stack
static vector<int> st;
st.clear();
for(int i = 0; i < sz; i++){
int u = vs[i];
int 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].push_back({idu, (int)w});
vt[idu].push_back({top, (int)w});
}
st.push_back(idu);
}
// 6) multi-source init
const long long INF = LLONG_MAX/4;
static vector<long long> da, db;
da.assign(sz, INF);
db.assign(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;
// 7) two-pass DP trên cây để lấy min(da[x]+db[x])
long long ans = INF;
function<void(int,int)> dfs1 = [&](int u, int p){
for(auto &e : vt[u]){
int v = e.first, 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]);
};
function<void(int,int)> dfs2 = [&](int u, int p){
for(auto &e : vt[u]){
int v = e.first, 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);
}
};
// st[0] chứa idx của nút có tin nhỏ nhất => gốc virtual tree
dfs1(st[0], -1);
dfs2(st[0], -1);
return ans;
}
void Init(int n,int u[],int v[],int w[]) {
for(int i=0;i<n;++i) adj[i].clear();
for(int i=0;i<n-1;++i) {
adj[u[i]].push_back({v[i],w[i]});
adj[v[i]].push_back({u[i],w[i]});
}
tt=0;
dep[0]=0;
dtr[0]=0;
lg=floor(log2(n));
up.assign(n,vector<int>(lg+1,-1));
dfs(0,-1);
}
long long Query(int s,int x[],int t,int y[]) {
return solve(x,s,y,t);
}
