#include <bits/stdc++.h>
#define rep(i,n)for(int i=0;i<(n);i++)
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;
#include "factories.h"
struct Segtree{
int N;
vector<P>dat;
Segtree(){}
Segtree(vector<P>v){
N=1;while(N<v.size())N<<=1;
dat=vector<P>(2*N);
for(int i=2*N-1;i>=1;i--){
if(i>=N){
if(i-N>=v.size())dat[i]=P(INF,-1);
else dat[i]=v[i-N];
}
else dat[i]=min(dat[i*2],dat[i*2+1]);
}
}
int query(int l,int r){
l+=N;r+=N;
P res(INF,-1);
while(l<r){
if(l&1)res=min(res,dat[l++]);
if(r&1)res=min(res,dat[--r]);
l>>=1;
r>>=1;
}
return res.second;
}
};
int n;
vector<P>E[600000];
int vid[600000];
vector<P>vs;
ll d[600000],depth[600000];
Segtree seg;
void dfs(int v,int p,ll dep){
depth[v]=dep;
vid[v]=vs.size();
vs.push_back(P(depth[v],v));
for(auto u:E[v]){
if(u.second==p)continue;
dfs(u.second,v,dep+u.first);
vs.push_back(P(depth[v],v));
}
}
int lca(int u,int v){
return seg.query(min(vid[u],vid[v]),max(vid[u],vid[v])+1);
}
ll dist(int u,int v){
int p=lca(u,v);
return depth[u]+depth[v]-depth[p]*2;
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
rep(i,n-1){
E[A[i]].push_back(P(D[i],B[i]));
E[B[i]].push_back(P(D[i],A[i]));
}
dfs(0,-1,0);
seg=Segtree(vs);
}
long long Query(int S, int X[], int T, int Y[]) {
if(S<=10&&T<=10){
ll Min=INF;
rep(i,S)rep(j,T){
Min=min(Min,dist(X[i],Y[j]));
}
return Min;
}
if(n<=5000){
priority_queue<P,vector<P>,greater<P>>que;
rep(i,n)d[i]=INF;
rep(i,S){
d[X[i]]=0;
que.push(P(0,X[i]));
}
while(!que.empty()){
P p=que.top();que.pop();
if(d[p.second]!=p.first)continue;
for(P u:E[p.second]){
if(d[u.second]>p.first+u.first){
d[u.second]=p.first+u.first;
que.push(P(d[u.second],u.second));
}
}
}
ll Min=INF;
rep(i,T)Min=min(Min,d[Y[i]]);
return Min;
}
abort();
}
