#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
using namespace std;
const int LOG=19;
const ll INF=1e18;
int n;
vector<vector<pair<int,int>>>adj;
vector<ll>dis1;
vector<int>tin,tout;
vector<vector<int>>par;
int dfs(int u=0,int p=-1,int t=0){
tin[u]=t++;
for(auto[v,d]:adj[u]){
if(v==p)continue;
par[0][v]=u;
dis1[v]=dis1[u]+d;
t=dfs(v,u,t);
}
tout[u]=t++;
return t;
}
int isanc(int u,int v){
return tin[u]<=tin[v]&&tout[v]<=tout[u];
}
int lca(int u,int v){
if(isanc(u,v))return u;
if(isanc(v,u))return v;
for(int i=LOG-1;i>=0;i--){
if(!isanc(par[i][u],v))u=par[i][u];
}
return par[0][u];
}
ll dis(int u,int v){
return dis1[u]+dis1[v]-2*dis1[lca(u,v)];
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
adj.assign(n,{});
dis1.assign(n,0);
tin.assign(n,0);
tout.assign(n,0);
par.assign(LOG,vector<int>(n));
par[0][0]=0;
for(int i=0;i<n-1;i++){
int u=A[i];
int v=B[i];
int d=D[i];
adj[u].push_back({v,d});
adj[v].push_back({u,d});
}
dfs();
for(int i=1;i<LOG;i++){
for(int u=0;u<n;u++){
int v=par[i-1][u];
par[i][u]=par[i-1][v];
}
}
}
ll Query(int S, int X[], int T, int Y[]) {
ll res=INF;
for(int i=0;i<S;i++){
int u=X[i];
for(int j=0;j<T;j++){
int v=Y[j];
res=min(res,dis(u,v));
}
}
return res;
}
