#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define fi first
#define se second
using namespace std;
const int N = 5e5 + 5;
const int LOG = log2(N) + 2;
const ll INF = 1e18 + 5;
vector<pair<int,int> > g[N];
ll dist[N];
int par[N][LOG];
int tin[N], tout[N], tt;
void dfs(int u, int p)
{
tin[u] = ++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, d] : g[u])
{
if(v != p)
{
dist[v] = dist[u] + d;
dfs(v, u);
}
}
tout[u] = tt;
}
void Init(int N, int A[], int B[], int D[])
{
for(int i = 0;i < N;i++)
{
int u = A[i], v = B[i], d = D[i];
g[u].pb({v, d});
g[v].pb({u, d});
}
dfs(0, 0);
}
bool isanc(int u, int v)
{
return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}
int get_lca(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];
}
ll Query(int S, int X[], int T, int Y[])
{
ll best = INF;
for(int i = 0;i < S;i++)
{
for(int j = 0;j < T;j++)
{
int lca = get_lca(X[i], Y[j]);
ll tot = dist[X[i]] + dist[Y[j]] - 2 * dist[lca];
best = min(best, tot);
}
}
return best;
}
