#include "factories.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pii pair<int, int>
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define ll long long
using namespace std;
const ll INF = 1e18;
const int MAXN = (int)5e5 + 5;
const int MAXQ = (int)1e5 + 5;
const int L = 20;
vector <pii> g[MAXN];
int n;
int pr[MAXN][L + 1];
ll d[MAXN];
int tin[MAXN], tout[MAXN], tiktak;
void precalc(int v, int par, ll len) {
tin[v] = ++tiktak;
pr[v][0] = par;
d[v] = len;
for (int lv = 1; lv <= L; lv++) {
pr[v][lv] = pr[pr[v][lv - 1]][lv - 1];
}
for (auto [to, dist] : g[v]) {
if (to == par) {
continue;
}
precalc(to, v, len + dist);
}
tout[v] = tiktak;
}
bool father(int a, int b) {
return tin[a] <= tin[b] && tout[b] <= tout[a];
}
int get_lca(int a, int b) {
if (father(a, b)) {
return a;
}
if (father(b, a)) {
return b;
}
for (int lv = L; lv >= 0; lv--) {
if (!father(pr[a][lv], b)) {
a = pr[a][lv];
}
}
return pr[a][0];
}
ll get_dist(int a, int b) {
return d[a] + d[b] - (2ll * d[get_lca(a, b)]);
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < n; i++) {
int u = A[i];
int v = B[i];
int dist = D[i];
g[u].pb({v, dist});
g[v].pb({u, dist});
}
precalc(0, 0, 0);
}
ll Query(int S, int X[], int T, int Y[]) {
ll ans = INF;
for (int i = 0; i < S; i++) {
for (int j = 0; j < T; j++) {
ans = min(ans, get_dist(X[i], Y[j]));
}
}
return ans;
}
