#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb(e) push_back(e)
#define mp(a,b) make_pair(a,b)
#define vf first
#define vs second
const int N = 500002,L=20;
vector<pair<int,int>> adj[N];
bool vis[N];
int siz[N],n;
ll res[N];
vector<pair<int,ll>> v[N];
void size_init(int node , int par){
siz[node] = 1;
for(auto i : adj[node]){
if(i.vf != par && !vis[i.vf]){
size_init(i.vf,node);
siz[node] += siz[i.vf];
}
}
}
int find_centroid(int node , int par , int total){
for(auto i : adj[node]){
if(!vis[i.vf] && i.vf != par && siz[i.vf] >= total/2)return find_centroid(i.vf , node , total);
}
return node;
}
void pre_dfs(int node , int par , int root , ll distance){
v[node].pb(mp(root,distance));
for(auto i : adj[node]){
if(!vis[i.vf] && i.vf != par){
pre_dfs(i.vf , node , root , distance + i.vs);
}
}
}
void centroid_decomposition(int node ,int par){
size_init(node , node);
node = find_centroid(node , node , siz[node]);
pre_dfs(node , node , node , 0);
vis[node] = 1;
for(auto i : adj[node]){
if(!vis[i.vf]){
centroid_decomposition(i.vf , node);
}
}
}
void Init(int nn, int A[], int B[], int D[]) {
n = nn;
for(int i = 0; i < n-1; i++){
adj[A[i]].pb(mp(B[i],D[i]));
adj[B[i]].pb(mp(A[i],D[i]));
}
memset(vis,0,sizeof vis);
centroid_decomposition(0,-1);
memset(res,-1,sizeof res);
}
long long Query(int a, int X[], int b, int Y[]) {
ll ans = 1e18;
for(int i = 0; i < a; i++){
for(auto it : v[X[i]]){
if(res[it.vf] == -1)res[it.vf] = it.vs;
else res[it.vf] = min(res[it.vf] , it.vs);
}
}
for(int i = 0; i < b; i++){
for(auto it : v[Y[i]]){
if(res[it.vf] != -1){
ans = min(ans , res[it.vf] + it.vs);
}
}
}
for(int i = 0; i < a; i++){
for(auto it : v[X[i]]){
res[it.vf] = -1;
}
}
return ans;
}
