#include "factories.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define iii tuple<int,int,int>
#define int long long
using namespace std;
vector<vector<int>> up(500005, vector<int>(20, -1));
int dist[500005][2];
vector<vector<pair<int,int>>> al(500005);
vector<int> in(500005, -1);
int t=0;
int depth[500005], distroot[500005];
void dfs(int x, int p){
in[x]=t++;
for(auto [to, d]:al[x]){
if(to==p)continue;
depth[to]=depth[x]+1;
distroot[to]=distroot[x]+d;
up[to][0]=x;
dfs(to, x);
}
}
int kpar(int x, int k){
for(int i=0;i<20;i++){
if((1<<i)&k)x=up[x][i];
}
return x;
}
int ispar(int a, int b){
if(depth[a]>depth[b])swap(a,b);
if(kpar(b, depth[b]-depth[a])==a)return true;
return false;
}
int lca(int a, int b){
if(depth[a] < depth[b])swap(a,b);
a=kpar(a, depth[a]-depth[b]);
for(int i=19;i>=0;i--){
if(up[a][i]==up[b][i])continue;
a=up[a][i], b=up[b][i];
}
return up[a][0];
}
void Init(signed N, signed A[], signed B[], signed D[]) {
for(int i=0;i<N;i++){
al[A[i]].push_back({B[i],D[i]});
al[B[i]].push_back({A[i],D[i]});
}
dfs(0, -1);
for(int i=1;i<20;i++){
for(int j=0;j<N;j++){
if(up[j][i-1] != -1)up[j][i]=up[up[j][i-1]][i-1];
}
}
//~ for(int i=0;i<N;i++){
//~ cout<<depth[i]<<endl;
//~ }
//~ printf("lca of 3 5 is %lld\n", lca(3, 5));
}
long long Query(signed S, signed X[], signed T, signed Y[]) {
vector<int> nodes;
for(int i=0;i<S;i++)nodes.push_back(X[i]);
for(int i=0;i<T;i++)nodes.push_back(Y[i]);
sort(nodes.begin(),nodes.end(),[&](auto a, auto b){
return in[a]<in[b];
});
for(int i=0;i<S+T-1;i++){
int l=lca(nodes[i], nodes[i+1]);
//~ printf("%lld %lld : %lld\n", nodes[i], nodes[i+1], l);
nodes.push_back(l);
}
sort(nodes.begin(),nodes.end(),[&](auto a, auto b){
return in[a]<in[b];
});
nodes.erase(unique(nodes.begin(),nodes.end()), nodes.end());
for(auto it:nodes){
al[it].clear();
dist[it][0]=dist[it][1]=1e15;
}
priority_queue<iii,vector<iii>,greater<iii>> pq;
for(int i=0;i<S;i++){
dist[X[i]][0]=0;
pq.push({0, X[i], 0});
}
for(int i=0;i<T;i++){
dist[Y[i]][1]=0;
if(dist[Y[i]][0]==0)return 0;
pq.push({0, Y[i], 1});
}
vector<int> stk;
stk.push_back(nodes[0]);
for(int i=1;i<(int)nodes.size();i++){
while(!ispar(stk.back(), nodes[i])){
stk.pop_back();
}
int sd=abs(distroot[nodes[i]]-distroot[stk.back()]);
al[nodes[i]].push_back({stk.back(), sd});
al[stk.back()].push_back({nodes[i], sd});
stk.push_back(nodes[i]);
}
//~ for(auto it : nodes){
//~ printf("node %lld: ",it);
//~ for(auto [to, d] : al[it]){
//~ printf("(%lld, %lld) ",to,d);
//~ }
//~ cout<<endl;
//~ }
int ans=1e15;
while(!pq.empty()){
auto [cd, x, st] = pq.top();pq.pop();
if(dist[x][st]<cd)continue;
for(auto [to, d]:al[x]){
int cand=cd+d;
if(dist[to][st]<cand)continue;
dist[to][st]=cand;
pq.push({cand, to, st});
}
}
for(auto it:nodes){
ans=min(ans, dist[it][0]+dist[it][1]);
}
//~ for(auto it:nodes){
//~ printf("%lld, dist0: %lld dist1: %lld\n", it, dist[it][0], dist[it][1]);
//~ }
return ans;
}
