#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
const bool multiTest = false;
#define task "C"
#define fi first
#define se second
#define MASK(i) (1LL << (i))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define BIT(mask, i) ((mask) >> (i) & 1)
template<typename T1, typename T2> bool minimize(T1 &a, T2 b) {
if (a > b) a = b; else return 0; return 1;
}
template<typename T1, typename T2> bool maximize(T1 &a, T2 b) {
if (a < b) a = b; else return 0; return 1;
}
const long long oo = 1e18 + 7;
const int MAX = 500050;
int N, Q;
int sz[MAX];
bool rem[MAX];
long long minDist[MAX];
vector<pair<int, int>> adj[MAX];
vector<pair<int, long long>> ancestors[MAX];
int dfsSZ(int u, int p) {
sz[u] = 1;
for (auto &[v, w]: adj[u]) if (v != p && !rem[v]) {
sz[u] += dfsSZ(v, u);
}
return sz[u];
}
int findCentroid(int u, int p, int n) {
for (auto &[v, w]: adj[u]) if (v != p && !rem[v]) {
if (2 * sz[v] > n)
return findCentroid(v, u, n);
}
return u;
}
void decomposition(int u, int p) {
int c = findCentroid(u, p, dfsSZ(u, p)); rem[c] = 1;
queue<tuple<int, int, long long>> q;
q.emplace(c, p, 0);
while (q.size()) {
auto [u, p, dist] = q.front(); q.pop();
ancestors[u].emplace_back(c, dist);
for (auto &[_u, _w]: adj[u]) if (_u != p && !rem[_u]) {
q.emplace(_u, u, dist + _w);
}
}
for (auto &[v, w]: adj[c]) if (v != c && !rem[v]) {
decomposition(v, c);
}
}
void Init(int _N, int _A[], int _B[], int _D[]) {
N = _N;
for (int i = 0; i < N - 1; ++i) {
adj[_A[i]].emplace_back(_B[i], _D[i]);
adj[_B[i]].emplace_back(_A[i], _D[i]);
}
decomposition(0, -1);
for (int i = 0; i < N; ++i) {
minDist[i] = oo;
rem[i] = 0;
}
}
void update(int v, int t) {
for (auto &[c, dist]: ancestors[v]) {
long long &dp = minDist[c];
if (!t) dp = oo; else minimize(dp, dist);
}
}
long long get(int v) {
long long res = oo; for (auto &[c, dist]: ancestors[v]) minimize(res, dist + minDist[c]);
return res;
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < T; ++i) {
update(Y[i], 1);
}
long long res = oo;
for (int i = 0; i < S; ++i) {
minimize(res, get(X[i]));
}
for (int i = 0; i < T; ++i) {
update(Y[i], 0);
}
return res;
}
