#include"factories.h"
#include<bits/stdc++.h>
#ifndef EVAL
#include"grader.cpp"
#endif
template<class T>void umin(T &a,T b){if(b<a)a=b;}
using namespace std;
typedef long long ll;
vector<pair<int,int>>g[500001];
int sz[500001];
bool black[500001];
void build_sz(int v,int p){
sz[v]=1;
for(auto &[to,wegiht]:g[v])if(to!=p&&!black[to]){
build_sz(to,v);
sz[v]+=sz[to];
}
}
int get_centroid(int v,int p){
int siz=sz[v]>>1;
while(true){
bool can=true;
for(auto &[to,weight]:g[v]){
if(black[to]||to==p)continue;
if(sz[to]>siz){
can=false;
p=v;
v=to;
break;
}
}
if(can)return v;
}
}
ll dist[20][500001];
void build_dist(int v,int p,int lv){
for(auto &[to,weight]:g[v])if(to!=p&&!black[to]){
dist[lv][to]=dist[lv][v]+weight;
build_dist(to,v,lv);
}
}
int parent[500001];
int level[500001];
ll mn[500001];
int n;
void decompose(int centroid,int parent_centroid){
build_sz(centroid,0);
centroid=get_centroid(centroid,0);
parent[centroid]=parent_centroid;
level[centroid]=level[parent_centroid]+1;
build_dist(centroid,0,level[centroid]);
black[centroid]=true;
for(auto &[to,weight]:g[centroid])if(!black[to])decompose(to,centroid);
}
void Init(int n,int a[],int b[],int c[]){
::n=n;
for(int i=0;i<n-1;i++){
int &x=a[i];
int &y=b[i];
int &z=c[i];
g[x+1].emplace_back(y+1,z);
g[y+1].emplace_back(x+1,z);
}
level[0]=-1;
decompose(1,0);
for(int i=1;i<=n;i++)mn[i]=1e15;
}
ll Query(int s,int x[],int t,int y[]){
for(int i=0;i<s;i++){
int ver=x[i]+1;
while(ver){
umin(mn[ver],dist[level[ver]][x[i]+1]);
ver=parent[ver];
}
}
ll ans=1e15;
for(int i=0;i<t;i++){
int ver=y[i]+1;
while(ver){
umin(ans,mn[ver]+dist[level[ver]][y[i]+1]);
ver=parent[ver];
}
}
for(int i=0;i<s;i++){
int ver=x[i]+1;
while(ver){
mn[ver]=1e15;
ver=parent[ver];
}
}
return ans;
}
