#include "factories.h"
#include <bits/stdc++.h>
#define F first
#define S second
#pragma optimize("O3")
using namespace std;
const int N=500005;
long long dist[N],hi[N];
int dp[N][20];
vector<pair<int,int> > adj[N];
int n;
long long ss[N];
int par[N],sz[N],del[N];
long long dist2[N][20];
int lab[N],rlab[N];
int nc;
void dfs0(int node,int pa=0)
{
/*dp[node][0]=pa;
for(int i=1;i<20;i++)
dp[node][i]=dp[dp[node][i-1]][i-1];*/
for(int i=0;i<adj[node].size();i++)
{
int x=adj[node][i].F,l=adj[node][i].S;
if(x==pa) continue;
dist[x]=dist[node]+l;
hi[x]=hi[node]+1;
dfs0(x,node);
}
}
int eul[2*N];
int reul[N];
int eulc=1;
void geteul(int node,int pa=-1)
{
eul[eulc++]=node;
reul[node]=eulc-1;
for(int i=0;i<adj[node].size();i++)
{
if(adj[node][i].F==pa) continue;
geteul(adj[node][i].F,node);
eul[eulc++]=node;
}
}
void bfs()
{
queue<int> q;
q.push(1);
int x=1;
while(q.size())
{
int cur=q.front();
lab[cur]=x;
rlab[x++]=cur;
q.pop();
for(int i=0;i<adj[cur].size();i++)
{
if(!lab[adj[cur][i].F]) q.push(adj[cur][i].F);
}
}
geteul(1);
for(int i=1;i<eulc;i++)
dp[i][0]=eul[i];
for(int i=1;i<20;i++)
{
for(int j=1;j<eulc;j++)
{
if(j+(1<<i)<eulc)
dp[j][i]=min(dp[j][i-1],dp[j+(1<<(i-1))][i-1]);
}
}
}
void dfs1(int node,int pa=0)
{
sz[node]=1;
nc++;
for(int i=0;i<adj[node].size();i++)
{
int x=adj[node][i].F,l=adj[node][i].S;
if(x==pa) continue;
if(del[x]) continue;
dfs1(x,node);
sz[node]+=sz[x];
}
}
int getCentroid(int node,int pa=0)
{
for(int i=0;i<adj[node].size();i++)
{
int x=adj[node][i].F,l=adj[node][i].S;
if(x==pa) continue;
if(del[x]) continue;
if(sz[x]>nc/2)
return getCentroid(x,node);
}
return node;
}
void decompose(int node,int pa=-1,int dep=0)
{
assert(dep<=21);
nc=0;
dfs1(node,node);
int centroid=getCentroid(node,node);
if(pa==-1) pa=centroid;
par[centroid]=pa;
del[centroid]=1;
for(int i=0;i<adj[centroid].size();i++)
{
int x=adj[centroid][i].F;
if(!del[x]) decompose(x,centroid,dep+1);
}
}
int lca(int x,int y)
{
/*if(hi[x]<hi[y]) swap(x,y);
for(int i=19;i>=0;i--)
{
if(hi[x]-(1<<i)>=hi[y])
x=dp[x][i];
}
if(x==y) return x;
for(int i=19;i>=0;i--)
{
if(dp[x][i]!=dp[y][i])
{
x=dp[x][i]; y=dp[y][i];
}
}
return dp[x][0];*/
int s=reul[x],e=reul[y];
if(s>e) swap(s,e);
int len=e-s+1;
len=log2(len);
return rlab[min(dp[s][len],dp[e-(1<<len)+1][len])];
}
long long getDist(int x,int y)
{
return dist[x]+dist[y]-2*dist[lca(x,y)];
}
void add(int x)
{
int lev=0;
int z=x;
while(true)
{
dist2[x][lev]=(dist2[x][lev]==-1?getDist(z,x):dist2[x][lev]);
ss[z]=min(ss[z],dist2[x][lev]);
lev++;
assert(lev<=20);
if(par[z]==z) break;
z=par[z];
}
}
void delet(int x)
{
int z=x;
int lev=0;
while(true)
{
ss[z]=(1LL<<60);
lev++;
assert(lev<=20);
if(par[z]==z) break;
z=par[z];
}
}
long long query(int x)
{
long long ans=(1LL<<60);
int z=x;
int lev=0;
while(true)
{
dist2[x][lev]=(dist2[x][lev]==-1?getDist(z,x):dist2[x][lev]);
ans=min(ans,dist2[x][lev]+ss[z]);
lev++;
assert(lev<=20);
if(par[z]==z) break;
z=par[z];
}
return ans;
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for(int i=0;i<N-1;i++)
{
A[i]++; B[i]++;
adj[A[i]].push_back({B[i],D[i]});
adj[B[i]].push_back({A[i],D[i]});
}
//cerr << "DONE" << endl;
dfs0(1);
//cerr << "DONE" << endl;
decompose(1);
bfs();
memset(dist2,-1,sizeof dist2);
for(int i=1;i<=N;i++)
ss[i]=(1LL<<60);
//cerr << "DONE" << endl;
}
long long Query(int S, int X[], int T, int Y[]) {
long long ans=(1LL<<60);
for(int i=0;i<S;i++) X[i]++;
for(int i=0;i<T;i++) Y[i]++;
for(int i=0;i<S;i++) add(X[i]);
for(int i=0;i<T;i++) ans=min(ans,query(Y[i]));
for(int i=0;i<S;i++) delet(X[i]);
return ans;
}
