#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#ifdef LOCAL
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
cerr<<vars<<" = ";
string delim="";
(...,(cerr<<delim<<values,delim=", "));
cerr<<"\n";
}
#else
#define deb(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {}
#endif
#define pb push_back
#define sz(x) (int)(x.size())
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T> inline void maxa(T& a,T b){a=max(a,b);}
template<typename T> inline void mina(T& a,T b){a=min(a,b);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int mxN=5e5+5,mxL=20; //make sure this is right
const int mod=1e9+7;
/*
build a virtual tree
for each node find the closest A and B
*/
vector<pii> graph[mxN];
vector<int> vt[mxN];
ll up[mxN][2],down[mxN][2],yes[mxN][2],bl[mxN][mxL],st[mxN],en[mxN],ht[mxN],dep[mxN],cur;
ll ans=1e18;
void dfs(int at,int p){
bl[at][0]=~p?p:at;
for(int i=1;i<mxL;i++)
bl[at][i]=bl[bl[at][i-1]][i-1];
st[at]=++cur;
for(auto &[i,w]:graph[at]){
if(i==p)
continue;
ht[i]=ht[at]+1;
dep[i]=dep[at]+w;
dfs(i,at);
}
en[at]=++cur;
}
int jump(int a,int k){
for(int i=0;i<mxL;i++){
if(k&(1<<i))
a=bl[a][i];
}
return a;
}
int lca(int a,int b){
if(ht[a]>ht[b])
swap(a,b);
int diff=ht[b]-ht[a];
b=jump(a,diff);
if(a==b)
return a;
for(int i=mxL-1;i>=0;i--){
if(bl[a][i]!=bl[b][i]){
a=bl[a][i];
b=bl[b][i];
}
}
return bl[a][0];
}
ll dist(int a,int b){
return dep[b]-dep[a];
}
bool anc(int a,int b){
return st[a]<=st[b] && en[a]>=en[b];
}
void dfs1(int at,int p){
down[at][0]=down[at][1]=1e16;
for(int &i:vt[at]){
if(i==p)
continue;
dfs1(i,at);
mina(down[at][0],down[i][0]+dist(at,i));
mina(down[at][1],down[i][1]+dist(at,i));
}
if(yes[at][0])
down[at][0]=0;
if(yes[at][1])
down[at][1]=0;
}
void dfs2(int at,int p){
for(int &i:vt[at]){
if(i==p)
continue;
up[i][0]=min(up[at][0],down[at][0])+dist(at,i);
up[i][1]=min(up[at][1],down[at][1])+dist(at,i);
dfs2(i,at);
}
mina(ans,min(up[at][0],down[at][0])+min(up[at][1],down[at][1]));
}
void solve(int root){
ans=1e18;
dfs1(root,-1);
dfs2(root,-1);
}
void build(vector<int> a){
sort(a.begin(),a.end(),[&](int x,int y){return st[x]<st[y];});
int len=sz(a);
for(int i=0;i<len-1;i++){
a.pb(lca(a[i],a[i+1]));
}
sort(a.begin(),a.end(),[&](int x,int y){return st[x]<st[y];});
a.resize(unique(a.begin(),a.end())-a.begin());
for(auto &i:a){
up[i][0]=up[i][1]=0;
down[i][0]=down[i][1]=0;
vt[i].clear();
}
stack<int> stk; stk.push(a[0]);
for(int i=1;i<sz(a);i++){
while(sz(stk)>=2 && !anc(stk.top(),a[i])){
int k=stk.top(); stk.pop();
vt[stk.top()].pb(k);
}
stk.push(a[i]);
}
while(sz(stk)>=2){
int k=stk.top();
stk.pop();
vt[stk.top()].pb(k);
}
solve(stk.top());
}
void Init(int N, int A[], int B[], int D[]){
for(int i=0;i<N;i++){
graph[A[i]].pb({B[i],D[i]});
graph[B[i]].pb({A[i],D[i]});
}
}
long long Query(int S, int X[], int T, int Y[]){
vector<int> a;
for(int i=0;i<S;i++){
yes[X[i]][0]=1;
a.pb(X[i]);
}
for(int i=0;i<T;i++){
yes[Y[i]][1]=1;
a.pb(Y[i]);
}
build(a);
for(int i=0;i<S;i++){
yes[X[i]][0]=0;
}
for(int i=0;i<T;i++){
yes[Y[i]][1]=0;
}
return ans;
}
