#include "factories.h"
#include <vector>
#include <algorithm>
#include <climits>
#include <iostream>
using namespace std;
const int nmax=500005;
vector< pair<int,long long> > v[nmax];
vector<int> ad[nmax];
long long lev[nmax],mn[nmax][2];
int tt[20][nmax];
int l[nmax],r[nmax],et[nmax];
int all[2*nmax],st[nmax];
long long ans;
int nr,i,j,n,aux,u;
bool comp(int unu,int doi)
{
return (l[unu]<l[doi]);
}
void dfs(int x)
{
int nod=0;
nr++;l[x]=nr;
for(int i=0;i<v[x].size();i++)
{
nod=v[x][i].first;
if(!l[nod])
{
lev[nod]=lev[x]+1LL*v[x][i].second;
tt[0][nod]=x;
dfs(nod);
}
}
r[x]=nr;
}
void deci_eram_la_un_chef()
{
for(i=1;i<=18;i++)
for(j=0;j<n;j++)
tt[i][j]=tt[i-1][tt[i-1][j]];
}
bool cup(int x,int y)
{
return (l[x]<=l[y]&&l[y]<=r[x]);
}
int lca(int A,int B)
{
for(int p=18;p>=0;p--)
{
aux=tt[p][A];
if(!(cup(aux,B)))
A=aux;
}
if(!(cup(A,B)))
A=tt[0][A];
return A;
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(int i=0;i<N-1;i++)
{
v[A[i]].push_back({B[i],D[i]});
v[B[i]].push_back({A[i],D[i]});
}
dfs(0);
deci_eram_la_un_chef();
}
void defeseu(int x)
{
int nod=0;
if(et[x])
mn[x][et[x]-1]=lev[x];
for(int i=0;i<ad[x].size();i++)
{
nod=ad[x][i];
defeseu(nod);
for(int it=0;it<2;it++)
ans=min(ans,mn[x][it]+mn[nod][1-it]-2*lev[x]);
for(int it=0;it<2;it++)
mn[x][it]=min(mn[x][it],mn[nod][it]);
}
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i=0;i<S;i++)
et[X[i]]=1;
for(int i=0;i<T;i++)
et[Y[i]]=2;
sort(X,X+S,comp);sort(Y,Y+T,comp);
merge(X,X+S,Y,Y+T,all,comp);
nr=S+T;
int x,y,t;
for(i=0;i<S+T-1;i++)
{
x=all[i];y=all[i+1];
t=lca(x,y);
if(t!=x&&t!=y) all[nr++]=t;
}
sort(all,all+nr,comp);u=0;
all[nr]=-1;
for(int i=0;i<nr;i++)
if(all[i]!=all[i+1])
{
while(u&&(!cup(st[u],all[i])))
u--;
if(u)ad[st[u]].push_back(all[i]);
st[++u]=all[i];
mn[all[i]][0]=mn[all[i]][1]=1LL*1e16;
}
ans=LLONG_MAX;
defeseu(all[0]);
for(int i=0;i<nr;i++)
ad[all[i]].clear(),et[all[i]]=0;
return ans;
}
