#include "factories.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<ll, ll>
using namespace std;
const ll M = 5e5+3, R=1e16, L=25;
int n;
vector<pii> graf[M];
int tin[M], tout[M], tt=0;
int par[M][L];
ll dist[M];
void dfs(int v, int p)
{
par[v][0] = p;
for(int i=1; i<L; i++)
par[v][i] = par[par[v][i-1]][i-1];
tin[v] = ++tt;
for(auto [u,d] : graf[v])
if(p != u)
dist[u] = dist[v]+d,
dfs(u,v);
tout[v] = ++tt;
}
bool isanc(int v, int u)
{
return (tin[v] <= tin[u] && tout[u] <= tout[v]);
}
int lca(int v, int u)
{
if(isanc(v,u)) return v;
if(isanc(u,v)) return u;
for(int i=L-1; i>=0; i--)
if(!isanc(par[v][i], u))
v = par[v][i];
return par[v][0];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i=0; i<N; i++)
graf[A[i]].push_back({B[i], D[i]}),
graf[B[i]].push_back({A[i], D[i]});
dfs(0,0);
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = R;
for(int i=0; i<S; i++)
for(int j=0; j<T; j++)
{
int u = X[i], v = Y[j];
int a = lca(u, v);
ans = min(ans, dist[u]+dist[v]-dist[a]*2);
}
return ans;
}
