#include <bits/stdc++.h>
using namespace std;
const int MAX = 500123;
const int LOG = 25;
int par[MAX][LOG];
int dep[MAX];
long long path[MAX];
vector<pair<int, int>> g[MAX];
void Dfs(int u, int p) {
par[u][0] = p;
for (int i = 1; i < LOG; i++) {
par[u][i] = par[par[u][i - 1]][i - 1];
}
for (auto e : g[u]) {
int v = e.first;
int w = e.second;
if (v == p) {
continue;
}
dep[v] = dep[u] + 1;
path[v] = path[u] + w;
Dfs(v, u);
}
}
int Lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = LOG - 1; i >= 0; i--) {
if (dep[par[u][i]] >= dep[v]) {
u = par[u][i];
}
}
for (int i = LOG - 1; i >= 0; i--) {
if (par[u][i] != par[v][i]) {
u = par[u][i];
v = par[v][i];
}
}
return (u == v ? u : par[u][0]);
}
long long dist(int u, int v) {
return path[u] + path[v] - 2 * path[Lca(u, v)];
}
int sz[MAX];
bool was[MAX];
vector<int> up[MAX];
void DfsSz(int u, int p) {
sz[u] = 1;
for (auto e : g[u]) {
int v = e.first;
if (!was[v] && v != p) {
DfsSz(v, u);
sz[u] += sz[v];
}
}
}
int FindCen(int u, int p, int n) {
for (auto e : g[u]) {
int v = e.first;
if (!was[v] && v != p && sz[v] * 2 >= n) {
return FindCen(v, u, n);
}
}
return u;
}
int Who(int u) {
DfsSz(u, u);
return FindCen(u, u, sz[u]);
}
void Update(int u, int p, int st) {
up[u].push_back(st);
for (auto e : g[u]) {
int v = e.first;
if (v == p || was[v]) {
continue;
}
Update(v, u, st);
}
}
void Find(int u) {
u = Who(u);
was[u] = true;
Update(u, u, u);
for (auto e : g[u]) {
int v = e.first;
if (!was[v]) {
Find(v);
}
}
}
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]].emplace_back(B[i], D[i]);
g[B[i]].emplace_back(A[i], D[i]);
}
Dfs(1, 0);
Find(1);
}
int lst[MAX];
int qId;
long long qdist[MAX];
long long Query(int S, int X[], int T, int Y[]) {
qId++;
for (int i = 0; i < S; i++) {
++X[i];
for (int j : up[X[i]]) {
lst[j] = qId;
qdist[j] = dist(X[i], j);
}
}
long long ans = 1e18;
for (int i = 0; i < T; i++) {
++Y[i];
for (int j : up[Y[i]]) {
if (lst[j] == qId) {
ans = min(ans, qdist[j] + dist(Y[i], j));
}
}
}
return ans;
}
