#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int mxN = 5e5 + 5, LG = 20;
const long long inf = 1e18;
int ord[mxN], sz[mxN], pr[mxN], spt[LG][2 * mxN];
long long dep[mxN], mn[mxN];
bool del[mxN];
vector<pair<int, int>> g[mxN];
int timer = 0;
void pre_dfs(int u) {
spt[0][ord[u] = ++timer] = u;
for (auto [v, w] : g[u]) {
if (!ord[v]) {
dep[v] = dep[u] + w;
pre_dfs(v);
spt[0][++timer] = u;
}
}
}
int mint(int u, int v) {
return ord[u] < ord[v] ? u : v;
}
int lca(int u, int v) {
int l = ord[u], r = ord[v];
if (l > r) {
swap(l, r);
}
int k = __lg(r - l + 1);
return mint(spt[k][l], spt[k][r - (1 << k) + 1]);
}
long long dis(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
void dfs(int u, int p) {
sz[u] = 1;
for (auto [v, w] : g[u]) {
if (!del[v] && v != p) {
dfs(v, u);
sz[u] += sz[v];
}
}
}
int findCen(int u, int p, int tot) {
for (auto [v, w] : g[u]) {
if (!del[v] && v != p && sz[v] * 2 > tot) {
return findCen(v, u, tot);
}
}
return u;
}
int split(int u) {
dfs(u, u);
u = findCen(u, u, sz[u]);
del[u] = 1;
for (auto [v, w] : g[u]) {
if (!del[v]) {
pr[split(v)] = u;
}
}
return u;
}
void ins(int u) {
for (int p = u; p; p = pr[p]) {
mn[p] = min(mn[p], dis(u, p));
}
}
void ers(int u) {
for (int p = u; p; p = pr[p]) {
mn[p] = inf;
}
}
long long get(int u) {
long long ans = inf;
for (int p = u; p; p = pr[p]) {
ans = min(ans, mn[p] + dis(p, u));
}
return ans;
}
void Init(int N, int *A, int *B, int *D) {
for (int i = 0; i < N - 1; ++i) {
++A[i], ++B[i];
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
pre_dfs(1);
for (int j = 1; j < LG; ++j) {
for (int i = 1; i + (1 << j) - 1 <= timer; ++i) {
spt[j][i] = mint(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
}
}
split(1);
fill(mn + 1, mn + N + 1, inf);
}
long long Query(int S, int *X, int T, int *Y) {
for (int i = 0; i < T; ++i) {
ins(++Y[i]);
}
long long res = inf;
for (int i = 0; i < S; ++i) {
res = min(res, get(++X[i]));
}
for (int i = 0; i < T; ++i) {
ers(Y[i]);
}
return res;
}
