#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,ll>
#define pll pair<long long,long long>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
using namespace std;
const int nmax=5e5+1;
int n;
vector<pii> adj[nmax];
ll pfx[nmax],treesize[nmax],vst[nmax],nxt[nmax][21],par[nmax],depth[nmax];
ll mn[nmax];
void pre_dfs(int u,int v)
{
treesize[u]=1;
FORD(i,adj[u])
{
if(i.fi==v || vst[i.fi]) continue;
pre_dfs(i.fi,u);
treesize[u]+=treesize[i.fi];
}
}
int centroid(int u,int v,int n)
{
FORD(i,adj[u])
{
if(i.fi==v || vst[i.fi]) continue;
if(treesize[i.fi]>n/2) return centroid(i.fi,u,n);
}
return u;
}
void dnc(int ct)
{
pre_dfs(ct,0);
vst[ct]=true;
FORD(i,adj[ct])
{
if(vst[i.fi]) continue;
int nxt_ct=centroid(i.fi,0,treesize[i.fi]);
par[nxt_ct]=ct;
dnc(nxt_ct);
}
}
void dfs(int u,int v)
{
FORD(i,adj[u])
{
if(i.fi==v) continue;
pfx[i.fi]=pfx[u]+i.se;
depth[i.fi]=depth[u]+1;
nxt[i.fi][0]=u;
dfs(i.fi,u);
}
}
void buildjump()
{
FOR(i,1,20) FOR(u,1,n) nxt[u][i]=-1;
FOR(i,1,20) FOR(u,1,n) nxt[u][i]=nxt[nxt[u][i-1]][i-1];
}
ll lca(int u,int v)
{
int preu=u,prev=v;
if(depth[u]<depth[v]) swap(u,v);
int dis=depth[u]-depth[v];
REP(i,20,0) if(dis&(1<<i)) u=nxt[u][i];
if(u==v) return pfx[preu]+pfx[prev]-pfx[u]*2;
REP(i,20,0) if(nxt[u][i]!=-1 && nxt[v][i]!=-1 && nxt[u][i]!=nxt[v][i])
{
u=nxt[u][i];
v=nxt[v][i];
}
return pfx[preu]+pfx[prev]-pfx[nxt[u][0]]*2;
}
void update(int x)
{
mn[x]=0;
int save=x;
while(par[save])
{
mn[par[save]]=min(mn[par[save]],lca(x,par[save]));
save=par[save];
}
}
void reset(int x)
{
int save=x;
while(par[save])
{
mn[par[save]]=L;
save=par[save];
}
}
ll get(int x)
{
ll ans=mn[x];
int save=x;
while(par[save])
{
if(mn[par[save]]!=L) ans=min(ans,mn[par[save]]+lca(x,par[save]));
save=par[save];
}
return ans;
}
void Init(int N, int A[], int B[], int D[])
{
n=N;
FOR(i,0,n-2)
{
adj[A[i]+1].push_back({B[i]+1,D[i]});
adj[B[i]+1].push_back({A[i]+1,D[i]});
}
//tim centroid dau tien
pre_dfs(1,0);
int ct=centroid(1,0,n);
dnc(ct);
dfs(1,0);
buildjump();
FOR(i,1,n) mn[i]=L;
}
long long Query(int S, int X[], int T, int Y[])
{
FOR(i,0,S-1) update(X[i]+1);
ll ans=L;
FOR(i,0,T-1) ans=min(ans,get(Y[i]+1));
FOR(i,0,S-1) reset(X[i]+1);
return ans;
}
