#include <bits/stdc++.h>
#include "factories.h"
#define pb push_back
#define fi first
#define se second
#define pii pair<ll,ll>
#define ll long long
using namespace std;
const int NN=5e5+5;
int LOG;
ll n;
vector<pair<int, ll>> kaimini[NN];
int tin[NN], tout[NN];
int t;
int par[NN][20];
ll att[NN];
void dfs(int u, int p, ll di){
att[u]=di;
t++;
tin[u]=t;
par[u][0]=p;
for(int i=1; i<LOG; i++){
par[u][i]=par[par[u][i-1]][i-1];
}
for(auto v : kaimini[u])
if(v.fi!=p)
dfs(v.fi, u, di+v.se);
t++;
tout[u]=t;
}
bool isanc(int u, int v){
return tin[u]<tin[v] && tout[v]<tout[u];
}
int getlca(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[u][i], v))
u=par[u][i];
}
return par[u][0];
}
void Init(int N, int A[], int B[], int D[]) {
LOG=0;
int pg=1;
while(pg<n)
LOG++, pg*=2;
n=N;
for(int i=0; i<N; i++){
kaimini[A[i]].pb({B[i], D[i]});
kaimini[B[i]].pb({A[i], D[i]});
}
dfs(0, 0, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
ll atb=LONG_LONG_MAX;
for(int i=0; i<S; i++){
int u=X[i];
for(int j=0; j<T; j++){
int v=Y[j];
int lca=getlca(u, v);
ll kop = att[u]+att[v]-2*att[lca];
atb=min(atb, kop);
}
}
return atb;
}
