#include <bits/stdc++.h>
#define INF 1000000000000000
#include "factories.h"
#define maxN 500005
using namespace std;
vector <int> e;
vector <pair<int,int>> adj[maxN];
long long n,d[maxN],s[maxN][21],p[maxN],l[maxN],dis[maxN],ds[2][maxN];
void dfs(int n,int par){
e.push_back(n);
for(int i=0;i<adj[n].size();i++){
if(adj[n][i].first==par) continue;
dis[adj[n][i].first]=dis[n]+adj[n][i].second;
d[adj[n][i].first]=d[n]+1;
dfs(adj[n][i].first,n);
e.push_back(n);
}
}
int minimum(int a,int b){
if(d[a]<d[b]) return a;
return b;
}
void Init(int N,int a[],int b[],int D[]){
n=N;
int i,j;
for(i=0;i<n-1;i++){
adj[a[i]].push_back({b[i],D[i]});
adj[b[i]].push_back({a[i],D[i]});
}
d[0]=0;
dis[0]=0;
dfs(0,-1);
l[1]=0;
for(i=0;i<n;i++){
p[i]=-1;
}
for(i=0;i<e.size();i++){
if(p[e[i]]==-1) p[e[i]]=i;
s[i][0]=e[i];
if(i<2) continue;
if(i==(i & -i)) l[i]=l[i-1]+1;
else l[i]=l[i-1];
}
for(j=1;j<21;j++){
for(i=0;i<e.size();i++){
if(i+(1<<(j-1))>e.size()) continue;
s[i][j]=minimum(s[i][j-1],s[i+(1<<(j-1))][j-1]);
}
}
}
void dfs2(int n,int par){
for(int i=0;i<adj[n].size();i++){
if(adj[n][i].first==par) continue;
dfs2(adj[n][i].first,n);
ds[0][n]=min(ds[0][n],ds[0][adj[n][i].first]+adj[n][i].second);
ds[1][n]=min(ds[1][n],ds[1][adj[n][i].first]+adj[n][i].second);
}
}
long long Query(int S,int x[],int T,int y[]){
if(S*T<=n){
int i,j,tmp,a,b,len;
long long ans=INF;
for(i=0;i<S;i++){
for(j=0;j<T;j++){
a=min(p[x[i]],p[y[j]]);
b=max(p[x[i]],p[y[j]]);
len=b-a+1;
tmp=minimum(s[a][l[len]],s[b-(1<<l[len])+1][l[len]]);
ans=min(ans,dis[x[i]]+dis[y[j]]-2*dis[tmp]);
}
}
return ans;
}
int i;
long long ans=INF;
for(i=0;i<n;i++) ds[0][i]=ds[1][i]=INF;
for(i=0;i<S;i++) ds[0][x[i]]=0;
for(i=0;i<T;i++) ds[1][y[i]]=0;
dfs2(0,-1);
for(i=0;i<n;i++) ans=min(ans,ds[0][i]+ds[1][i]);
return ans;
}
