#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, L, R) for (int i = (int)(L); i <= (int)(R); ++i)
#define FOD(i, R, L) for (int i = (int)(R); i >= (int)(L); --i)
#define FOA(x, A) for (auto &x : (A))
#define fs first
#define sd second
#define ii pair<int, int>
const int N = 500000 + 5;
const int oo = (int)1e18;
vector<ii> g[N];
int n;
// ---------------- LCA ----------------
struct LCA {
int up[N][21];
int h[N];
long long high[N];
void build(int u, int par) {
FOA(e, g[u]) {
int v = e.fs, w = e.sd;
if (v == par) continue;
h[v] = h[u] + 1;
high[v] = high[u] + w;
up[v][0] = u;
FOR(i, 1, 20) up[v][i] = up[up[v][i - 1]][i - 1];
build(v, u);
}
}
int get(int u, int v) {
if (h[v] < h[u]) swap(u, v);
int diff = h[v] - h[u];
FOR(i, 0, 20) if (diff >> i & 1) v = up[v][i];
if (u == v) return u;
FOD(i, 20, 0) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
long long path(int u, int v) {
int w = get(u, v);
return high[u] + high[v] - 2 * high[w];
}
} lca;
// ---------------- Centroid Decomposition ----------------
namespace Centroid {
int sz[N], parent[N];
bool cen[N];
long long nearCen[N];
void DFS_sz(int u, int par) {
sz[u] = 1;
FOA(e, g[u]) {
int v = e.fs;
if (v == par || cen[v]) continue;
DFS_sz(v, u);
sz[u] += sz[v];
}
}
int find_centroid(int u, int par, int total) {
FOA(e, g[u]) {
int v = e.fs;
if (v == par || cen[v]) continue;
if (sz[v] > total / 2) return find_centroid(v, u, total);
}
return u;
}
void build_tree(int u, int par) {
DFS_sz(u, -1);
int c = find_centroid(u, -1, sz[u]);
cen[c] = true;
parent[c] = par;
FOA(e, g[c]) {
int v = e.fs;
if (!cen[v]) build_tree(v, c);
}
}
void update(int u) {
int v = u;
while (v) {
nearCen[v] = min(nearCen[v], lca.path(u, v));
v = parent[v];
}
}
void clear_node(int u) {
int v = u;
while (v) {
nearCen[v] = oo;
v = parent[v];
}
}
long long query(int u) {
int v = u;
long long res = oo;
while (v) {
res = min(res, nearCen[v] + lca.path(u, v));
v = parent[v];
}
return res;
}
void init_all() {
FOR(i, 1, n) {
sz[i] = 0;
parent[i] = 0;
cen[i] = false;
nearCen[i] = oo;
}
}
} // namespace Centroid
using namespace Centroid;
// ---------------- API for the grader ----------------
void Init(int _N, int A[], int B[], int D[]) {
n = _N;
FOR(i, 1, n) g[i].clear();
FOR(i, 0, n - 2) {
int u = A[i] + 1;
int v = B[i] + 1;
int w = D[i];
g[u].push_back({v, w});
g[v].push_back({u, w});
}
// build LCA
lca.up[1][0] = 0;
lca.h[1] = 0;
lca.high[1] = 0;
lca.build(1, 0);
// build centroid tree
init_all();
build_tree(1, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
long long ans = oo;
vector<int> leftNodes;
FOR(i, 0, S - 1) {
int u = X[i] + 1;
leftNodes.push_back(u);
update(u);
}
FOR(i, 0, T - 1) {
int u = Y[i] + 1;
ans = min(ans, query(u));
}
FOA(x, leftNodes) clear_node(x);
return ans;
}
