#include "factories.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
pair<int,int> par[500005][30];
vector<pair<int,int>> adj[500005];
int depth[500005];
void dfs(int cur,int d){
depth[cur]=d;
for (auto [j,i]:adj[cur]){
if (par[cur][0].second==i) continue;
par[i][0]={j,cur};
dfs(i,d+1);
}
}
int dis(int x,int y){
int ret=0;
if (depth[x]<depth[y]) swap(x,y);
for (int k=19;k>=0;k--){
if (depth[par[x][k].second]>=depth[y]){
ret+=par[x][k].first;
x=par[x][k].second;
}
}
if (x==y) return ret;
for (int k=19;k>=0;k--){
if (par[x][k].second!=par[y][k].second){
ret+=par[x][k].first;
x=par[x][k].second;
ret+=par[y][k].first;
y=par[y][k].second;
}
}
return ret+par[x][0].first+par[y][0].first;
}
int n;
void Init(signed N, signed A[], signed B[], signed D[]) {
n=N;
for (int i=0;i<N-1;i++){
adj[A[i]+1].push_back({D[i],B[i]+1});
adj[B[i]+1].push_back({D[i],A[i]+1});
}
dfs(1,1);
for (int k=1;k<20;k++) for (int i=1;i<=N;i++) par[i][k]={par[i][k-1].first+par[par[i][k-1].second][k-1].first,par[par[i][k-1].second][k-1].second};
}
int Query(signed S, signed X[], signed T, signed Y[]){
int ret=1e18;
if (S*T<8000){
for (int i=0;i<S;i++){
for (int j=0;j<T;j++){
ret=min(ret,dis(X[i]+1,Y[j]+1));
}
}
return ret;
}
else{
if (S>T){
swap(S,T);
swap(X,Y);
}
unordered_set<int> st;
for (int i=0;i<T;i++) st.insert(Y[i]+1);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
vector<int> ans(n+1,1e18);
for (int i=0;i<S;i++){
pq.push({0,X[i]+1});
ans[X[i]+1]=0;
}
while (true){
auto pqt=pq.top();
pq.pop();
if (ans[pqt.second]<pqt.first) continue;
if (st.count(pqt.second)) return pqt.first;
for (auto [j,i]:adj[pqt.second]){
if (ans[i]<=j+pqt.first) continue;
ans[i]=j+pqt.first;
pq.push({ans[i],i});
}
}
}
}
