#include <bits/stdc++.h>
#include "factories.h"
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ar = array<int, 2>;
const int64_t INF = 1ll << 60;
const int N = 5e5 + 5, LG = 19;
int n, T, st[N], fn[N], pr[N][LG];
long long h[N], dist[N];
vector<ar> adj[N];
bool is_anc(int v, int p) {
return st[p] <= st[v] && fn[v] <= fn[p];
}
void dfs(int v, int p) {
pr[v][0] = p;
FOR(i, 0, LG - 1)
pr[v][i + 1] = pr[pr[v][i]][i];
st[v] = ++T;
for (auto [u, w]: adj[v]) if (u != p) {
h[u] = h[v] + w;
dfs(u, v);
}
fn[v] = ++T;
}
int LCA(int u, int v) {
if (is_anc(u, v)) return v;
if (is_anc(v, u)) return u;
for (int i = LG - 1; i >= 0; --i) if (!is_anc(u, pr[v][i]))
v = pr[v][i];
assert(!is_anc(u, v) && is_anc(u, pr[v][0]));
return pr[v][0];
}
void Init(int NV, int A[], int B[], int D[]) {
n = NV;
FOR(i, 0, n - 1) {
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0);
fill(dist, dist + N, INF);
}
int all[2 * N];
long long Query(int S, int X[], int T, int Y[]) {
FOR(i, 0, S) dist[X[i]] = 0;
copy(X, X + S, all);
copy(Y, Y + T, all + S);
int q = S + T, qq = q - 1;
sort(all, all + q, [&](const int u, const int v) {return st[u] < st[v];});
FOR(i, 0, q - 1) all[++qq] = LCA(all[i], all[i + 1]);
q = qq + 1;
sort(all, all + q, [&](const int u, const int v) {return fn[u] < fn[v];});
vector<int> cand;
FOR(i, 0, q) {
int t = all[i], w;
while (cand.size() && is_anc(w = cand.back(), t)) {
dist[t] = min(dist[t], dist[w] + h[w] - h[t]);
cand.pop_back();
}
cand.push_back(all[i]);
}
cand.clear();
sort(all, all + q, [&](const int u, const int v) {return st[u] < st[v];}); //reverse fn doroste aya?
FOR(i, 0, q) {
int t = all[i], w;
while (cand.size() && !is_anc(t, w = cand.back()))
cand.pop_back();
if (cand.size())
dist[t] = min(dist[t], dist[w] + h[t] - h[w]);
cand.push_back(all[i]);
}
long long mn = dist[Y[0]];
FOR(i, 1, T) mn = min(mn, dist[Y[i]]);
FOR(i, 0, q) dist[all[i]] = INF;
return mn;
}
