#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
#define MAX_N 500000
const ll inf=1e15, lg=19;
int n;
ll Dis[MAX_N];
int dpth[MAX_N];
vector<vector<int>>BB(MAX_N), AA(MAX_N);
int up[MAX_N][lg+1];
void pre(){
for(int i=0;i<MAX_N;i++){
Dis[i]=inf, dpth[i]=2*n;
}
}
void bfs(int ind){
queue<int>q;
q.push(ind);
up[ind][0]=ind;
Dis[ind]=dpth[ind]=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(int j=1;j<=lg;j++){
up[u][j]=up[up[u][j-1]][j-1];
if(up[u][j]==0)
break;
}
for(int i=0;i<AA[u].size();i++){
int v=AA[u][i];
if(dpth[u]+1<dpth[v]){
dpth[v]=dpth[u]+1, Dis[v]=Dis[u]+BB[u][i];
up[v][0]=u;
q.push(v);
}
}
}
}
int lca(int u, int v){
// u
// v
if(dpth[u]>dpth[v])
swap(u, v);
for(int j=lg;j>=0;j--){
if(dpth[up[v][j]]>=dpth[u])
v=up[v][j];
}
if(u==v)
return u;
for(int j=lg;j>=0;j--){
if(up[u][j]!=up[v][j])
u=up[u][j], v=up[v][j];
}
return up[v][0];
}
inline ll get_dis(int u, int v){
return Dis[u]+Dis[v]-2*Dis[lca(u, v)];
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
pre();
for(int i=0;i<n-1;i++){
int u=A[i], v=B[i], w=D[i];
AA[u].push_back(v);
AA[v].push_back(u);
BB[u].push_back(w);
BB[v].push_back(w);
}
bfs(0);
}
long long Query(int S, int X[], int T, int Y[]) {
if(S>45 && T>45){
vector<ll>D(n, inf);
vector<bool>In_y(n, 0), Vis(n, 0);
for(int i=0;i<T;i++){
In_y[Y[i]]=1;
}
priority_queue<array<ll, 2>>q;
for(int i=0;i<S;i++){
q.push({0, X[i]});
D[X[i]]=0;
}
while(!q.empty()){
int u=q.top()[1];
q.pop();
if(Vis[u])
continue;
Vis[u]=1;
if(In_y[u])
return D[u];
for(int i=0;i<AA[u].size();i++){
int v=AA[u][i], w=BB[u][i];
if(D[u]+w<D[v]){
D[v]=D[u]+w;
q.push({-D[v], v});
}
}
}
}
ll ans=inf;
for(int i=0;i<S;i++){
for(int j=0;j<T;j++){
ans=min(ans, get_dis(X[i], Y[j]));
}
}
return ans;
}
