#include "factories.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <vector>
#include <iomanip>
#include <string>
#include <queue>
#include <set>
#include <deque>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define ll long long
const ll inf=1e17;
#define MAX_N 500000+5
#define MAX_Q 100000+5
#define MAX_SUM_ST 1000000+5
#define MAX_VALUE 1000000000+5
#define fi first
#define se second
static int N, Q;
//map<pair<int,int>,ll>d;
int par[MAX_N];
vector<pair<int,ll>>ma[MAX_N];
//vector<int> ma_[MAX_N];
int sz[MAX_N];
//int vi[MAX_N];
ll ans[MAX_N];
bool dead[MAX_N];
int cur_n=0;
map<int,ll> dist[MAX_N];
//int gl;
void dfs_init(int x,int p=0)
{
sz[x]=1;
for(auto [y,w]:ma[x])
{
if(y^p)
dfs_init(y,x),sz[x]+=sz[y];
}
}
int find_centroid(int x)
{
for(auto [y,w]:ma[x])
{
if(!dead[y] and sz[y]>(cur_n>>1))
{
sz[x]-=sz[y];
sz[y]+=sz[x];
return find_centroid(y);
}
}
return x;
}
int cur;
void compute(int x,int p=0,ll d=0)
{
dist[x][cur]=d;
for(auto [y,w]:ma[x])
{
if(y!=p and !dead[y])
{
compute(y,x,d+w);
}
}
}
void build(int x,int pr=0)
{
cur_n=sz[x];
int cen=find_centroid(x);
par[cen]=pr;
dead[cen]=1;
cur=cen;
compute(cen);
for(auto [y,w]:ma[cen])
{
if(!dead[y])
{
build(y,cen);
// ma_[cen].push_back(ch);
}
}
// return cen;
}
int __p;
void Init(int n,int A[], int B[], int D[]){
__p=n;
for(int i=0;i<=n;i++){
ma[i].clear();
dead[i]=0;
dist[i].clear();
}
for (int i=0;i<n-1;i++){
int x=A[i],y=B[i];
x++;
y++;
ma[x].push_back({y,D[i]});
ma[y].push_back({x,D[i]});
// d[{x,y}]=d[{y,x}]=D[i];
}
dfs_init(1);
build(1);
for(int i=1;i<=__p;i++)ans[i]=inf;
}
vector<int> chg;
void change_color(ll x)
{
ll st=x;
while(x>0)
{
chg.push_back(x);
ans[x]=min(ans[x],dist[st][x]);
x=par[x];
}
}
ll answer(ll x)
{
ll st=x;
ll cur=inf;
//cout<<"P ";
while(x>0)
{
//cout<<x<<' ';
cur=min(cur,ans[x]+dist[st][x]);
x=par[x];
}
//cout<<endl;
return cur;
}
ll Query(int S,int X[],int T,int Y[]){
for(auto i:chg)ans[i]=inf;
chg.clear();
// for(int i=1;i<=__p;i++)ans[i]=1e18;
for(int i=0;i<S;i++)
{
change_color(X[i]+1);
//cout<<X[i]+1<<' ';
}
//cout<<endl;
ll fnl=inf;
for(int i=0;i<T;i++)
fnl=min(fnl,answer(Y[i]+1));
return fnl;
}
