#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
int n;
int timer;
int x,y;
long long depth[500005];
int dp[500005][20];
vector<pair<int,long long> > v[500005];
long long dp2[500005];
int pred[500005];
int tin[500005];
int tout[500005];
bool used[500005];
int sz;
int q[500005];
long long ans;
void dfs(int x,int y) {
tin[x]=++timer;
dp[x][0]=y;
for (int i=1;i<=19;++i)
dp[x][i]=dp[dp[x][i-1]][i-1];
for (int i=0;i<v[x].size();++i) {
int to=v[x][i].first;
if (to==y) continue;
depth[to]=depth[x];
depth[to]+=v[x][i].second;
dfs(to,x);
}
tout[x]=timer;
}
int cnt[500005];
int mx[500005];
void dfs1(int x,int y) {
q[++sz]=x;
cnt[x]=1;
mx[x]=0;
for (int i=0;i<v[x].size();++i) {
int to=v[x][i].first;
if (to==y || used[to]) continue;
dfs1(to,x);
cnt[x]+=cnt[to];
if (cnt[to]>mx[x]) {
mx[x]=cnt[to];
}
}
}
void build(int x,int y) {
sz=0;
dfs1(x,0);
int mn=1e9;
int c=x,xx;
int cur;
for (int i=1;i<=sz;++i) {
xx=q[i];
cur=max(mx[xx],cnt[x]-cnt[xx]);
if (cur<mn) {
mn=cur;
c=xx;
}
}
used[c]=true;
x=c;
pred[x]=y;
for (int i=0;i<v[x].size();++i) {
int to=v[x][i].first;
if (!used[to]) build(to,x);
}
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
int z;
for (int i=0;i<n-1;++i) {
x=A[i];
y=B[i];
++x; ++y;
z=D[i];
v[x].push_back(make_pair(y,z));
v[y].push_back(make_pair(x,z));
}
dfs(1,0);
build(1,0);
for (int i=1;i<=n;++i)
dp2[i]=1e15;
}
bool f_pred(int x,int y) {
return (tin[x]<=tin[y] && tout[x]>=tout[y]);
}
inline int get_lca(int x,int y) {
if (f_pred(x,y)) return x;
if (f_pred(y,x)) return y;
for (int i=19;i>=0;--i)
if (dp[x][i] && !f_pred(dp[x][i],y)) x=dp[x][i];
return dp[x][0];
}
inline long long get_dist(int x,int y) {
int z=get_lca(x,y);
return depth[x]+depth[y]-depth[z]-depth[z];
}
inline void update1(int x) {
int y=x;
long long xx;
while (y) {
xx=get_dist(x,y);
if (xx<dp2[y]) dp2[y]=xx;
y=pred[y];
}
}
inline void update2(int x) {
while (x) {
if (dp2[x]==1e15) return;
dp2[x]=1e15;
x=pred[x];
}
}
inline void solve(int x) {
int y=x;
long long xx;
while (y) {
xx=get_dist(x,y)+dp2[y];
if (xx<ans) ans=xx;
y=pred[y];
}
}
long long Query(int S, int X[], int T, int Y[]) {
ans=1e18;
int x;
for (int i=0;i<S;++i) {
x=X[i];
++x;
update1(x);
}
for (int i=0;i<T;++i) {
x=Y[i];
++x;
solve(x);
}
for (int i=-0;i<S;++i) {
x=X[i];
++x;
update2(x);
}
return ans;
}
