#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define show(n) cout<<n<<'\n'
#define all(v) v.begin(), v.end()
#define br cout<<"\n"
#define pb push_back
const int mxN = 5e5 + 10;
const long long inf = 1e18;
set<pair<int, int>> adj[mxN];
int out[mxN],sz[mxN],par[mxN],depth[mxN],parent[mxN];
long long sum[mxN], ans[mxN];
vector<vector<int>> dp;
vector<int> euler,lg;
struct fst_lca{
void dfs(int u,int p){
sz[u]=1;
out[u]=(int)euler.size();
euler.pb(u);
for(auto [v, w]:adj[u]){
if(v^p){
depth[v]=depth[u]+1;
sum[v] = (long long) sum[u] + w;
dfs(v,u);
sz[u]+=sz[v];
out[u]=(int)euler.size();
euler.pb(u);
}
}
}
void init_dp(){
int csz=euler.size();
lg.resize(csz+1);
for(int i=2;i<=csz;++i) lg[i]=lg[i>>1]+1;
dp=vector<vector<int>>(csz,vector<int>(lg[csz]+1));
for(int i=0;i<csz;i++) dp[i][0]=euler[i];
for(int j=1;j<=lg[csz];j++){
for(int i=0;i+(1<<(j-1))<csz;i++){
dp[i][j]=comp(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
}
int comp(int u,int v) {
return depth[u]<depth[v]?u:v;
}
int lca(int l,int r) {
return comp(dp[l][lg[r-l+1]],dp[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
long long dist(int u,int v){
if(out[u]>out[v]) swap(u,v);
return sum[u]+sum[v]-(sum[lca(out[u],out[v])]<<1);
}
} fst;
struct centroid{
void pre_sz(int u,int p){
sz[u]=1;
for(auto [v, w]:adj[u]){
if(v^p){
pre_sz(v,u);
sz[u]+=sz[v];
}
}
}
int find_cen(int u,int p,int r){
int mx=0,mxv;
for(auto [v, w]:adj[u]){
if(v^p&&sz[v]>mx){
mxv=v,mx=sz[v];
}
}
if(mx<=sz[r]>>1) return u;
return find_cen(mxv,u,r);
}
void decompose(int u=1,int p=-1){
pre_sz(u,-1);
int cent=find_cen(u,-1,u);
par[cent]=p;
for(auto [it, w]:adj[cent]){
adj[it].erase({cent, w});
decompose(it,cent);
}
adj[cent].clear();
}
void update(int u){
int c=u;
while(c!=-1){
ans[c]=min(ans[c],fst.dist(u,c));
c=par[c];
}
}
void undo(int u){
int c=u;
while(c!=-1){
ans[c] = inf;
c=par[c];
}
}
long long qry(int u){
int c=u;
long long res = inf;
while(c!=-1){
res=min(res,ans[c]+fst.dist(u,c));
c=par[c];
}
return res;
}
} cent;
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N; ++i) ans[i] = inf;
for(int i = 0; i < N - 1; ++i){
adj[A[i]].insert({B[i], D[i]});
adj[B[i]].insert({A[i], D[i]});
}
fst.dfs(0, -1);
fst.init_dp();
cent.decompose(0, -1);
}
long long Query(int S, int X[], int T, int Y[]) {
long long ans = inf;
for(int i = 0; i < S; ++i){
cent.update(X[i]);
}
for(int i = 0; i < T; ++i){
ans = min(ans, cent.qry(Y[i]));
}
for(int i = 0; i < S; ++i){
cent.undo(X[i]);
}
return ans;
}
