#include "factories.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>
#include <stdio.h>
#include <math.h>
#define ll long long
#define pii pair<long long, long long>
#define pb push_back
#define fi first
#define se second
using namespace std;
const int N = 5e5 +5;
const ll INF = 1e18 +5;
const int LOG=log2(N) +2;
vector<pii>graph[N];
ll tin[N], tout[N], tt, par[N][LOG], dist[N];
void dfs(ll u, ll p){
tin[u]=tt;
tt++;
par[u][0]=p;
for(int i=1; i<LOG; i++)
par[u][i]=par[par[u][i-1]][i-1];
for(auto v : graph[u]){
if(v.fi!=p){
dist[v.fi]=dist[u]+v.se;
dfs(v.fi, u);
}
}
tout[u]=tt;
}
bool isanc(ll u, ll v){
return (tin[u]<=tin[v] && tout[u]>=tout[v]);
}
ll lca(ll u, ll 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[]){
for(int i=0; i<N; i++){
graph[A[i]].pb({B[i], D[i]});
graph[B[i]].pb({A[i], D[i]});
}
dfs(0, 0);
}
long long Query(int S, int X[], int T, int Y[]){
ll mn=INF;
for(int i=0; i<S; i++){
for(int j=0; j<T; j++){
int x=lca(X[i], Y[j]);
mn=min(mn, dist[X[i]]-dist[x]+dist[Y[j]]-dist[x]);
}
}
return mn;
}
