//#include "grader.cpp"
//#include "factories.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int Nmax = 5e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = 3.14159265359;
vector <pair <int, int>> adj[Nmax];
long long d[Nmax];
long long mind[Nmax];
int anc[Nmax][20];
int par[Nmax];
int sz[Nmax];
int h[Nmax];
bool bk[Nmax];
void dfs(int u, int p = -1) {
anc[u][0] = p;
for (int i = 1; i < 20; i++) {
int pr = anc[u][i - 1];
if (pr < 0)
anc[u][i] = -1;
else
anc[u][i] = anc[pr][i - 1];
}
for (pair <int, int> to : adj[u]) {
int v = to.fi;
int w = to.se;
if (v == p)
continue;
h[v] = h[u] + 1;
d[v] = d[u] + w;
dfs(v, u);
}
}
long long dis(int u, int v) {
if (h[u] < h[v])
swap(u, v);
long long res = d[u] + d[v];
for (int i = 19; i >= 0; i--)
if (h[u] - (1 << i) >= h[v])
u = anc[u][i];
// cerr << u << " " << v << " " << h[u] << " " << h[v] << " " << res << "\n";
if (u == v)
return res - (d[v] << 1);
for (int i = 19; i >= 0; i--) if (anc[u][i] != anc[v][i]) {
u = anc[u][i];
v = anc[v][i];
}
return res - (d[anc[v][0]] << 1);
}
int calc(int u, int p = -1) {
sz[u] = 1;
for (pair <int, int> to : adj[u]) {
int v = to.fi;
if (v == p || bk[v])
continue;
sz[u] += calc(v, u);
}
return sz[u];
}
int getcen(int u, int S, int p = -1) {
for (pair <int, int> to : adj[u]) {
int v = to.fi;
if (v == p || bk[v] || (sz[v] << 1) <= S)
continue;
return getcen(v, S, u);
}
return u;
}
int centroid(int u) {
int r = getcen(u, calc(u));
bk[r] = true;
for (pair <int, int> to : adj[u]) {
int v = to.fi;
if (bk[v])
continue;
par[centroid(v)] = r;
}
return r;
}
void Init(int n, int a[], int b[], int d[]) {
for (int i = 0; i < n - 1; i++) {
adj[a[i]].push_back(mp(b[i], d[i]));
adj[b[i]].push_back(mp(a[i], d[i]));
}
dfs(0);
par[centroid(0)] = -1;
for (int i = 0; i < n; i++)
mind[i] = ooo;
}
void reset(int u) {
if (u < 0)
return;
mind[u] = ooo;
reset(par[u]);
}
void update(int u, int cur) {
if (cur < 0)
return;
// cerr << u << " " << cur << " " << dis(u, cur) << "\n";
mini(mind[cur], dis(u, cur));
update(u, par[cur]);
}
long long getans(int u, int cur) {
if (cur < 0)
return ooo;
// cerr << u << " " << cur << " " << dis(u, cur) << "\n";
long long res = mind[cur] + dis(u, cur);
mini(res, getans(u, par[cur]));
return res;
}
long long Query(int s, int x[], int t, int y[]) {
for (int i = 0; i < s; i++)
update(x[i], x[i]);
long long res = ooo;
for (int i = 0; i < t; i++)
mini(res, getans(y[i], y[i]));
for (int i = 0; i < s; i++)
reset(x[i]);
return res;
}
