#include <bits/stdc++.h>
//#define int long long
#define MASK(i) (1LL << (i))
using namespace std;
const long long inf = 1e18;
const int N = 5e5 + 5;
// 1-indexed Centroid Decomposition
//int __lg(int n) { return log2(n) + 0.0001; } // Microsoft Visualstudio doesn't have __lg function, this help error not occurrence =))
vector<pair<int, int>> G[N];
int sz[N], par_centroid[N], h[N] = {}, id[N] = {}, par[N][19];
bool del[N] = {};
long long d[N][19], ans[N], dpar[N][19];
int timer;
int dfs(int u, int p) {
sz[u] = 1;
for (auto v : G[u]) if (v.first != p && !del[v.first]) {
sz[u] += dfs(v.first, u);
}
return sz[u];
}
int centroid(int u, int p, int n) {
for (auto v : G[u]) if (v.first != p && !del[v.first]) {
if (sz[v.first] > n / 2) return centroid(v.first, u, n);
}
return u;
}
void build(int u, int p) {
int n = dfs(u, p);
int c = centroid(u, p, n);
par_centroid[c] = p;
del[c] = 1;
for (auto v : G[c]) {
if (!del[v.first])
build(v.first, c);
}
}
void first_dfs(int u, int p) {
for (auto v : G[u]) if (v.first != p) {
h[v.first] = h[u] + 1;
par[v.first][0] = u;
d[v.first][0] = v.second;
first_dfs(v.first, u);
}
}
long long get_dis(int u, int v)
{
long long dis = 0;
if (h[u] > h[v]) swap(u, v);
int k = h[v] - h[u];
int lg = (k == 0 ? -1 : __lg(k));
for (int i = 0; i <= lg; i++) if (k & MASK(i))
{
dis += d[v][i];
v = par[v][i];
}
if (v == u) return dis;
lg = (h[v] == 0 ? -1 : __lg(h[v]));
for (int i = lg; i >= 0; i--)
{
if (par[v][i] != par[u][i])
{
dis += d[v][i] + d[u][i];
v = par[v][i];
u = par[u][i];
}
}
return dis + d[v][0] + d[u][0];
}
void modify(int u) {
for (int v = u, level = 0; v != 0; v = par_centroid[v], level++)
{
if (id[v] == timer)
{
ans[v] = min(ans[v], dpar[u][level]);
}
else
{
id[v] = timer;
ans[v] = dpar[u][level];
}
}
}
long long query(int u) {
long long mn = inf;
for (int v = u, level = 0; v != 0; v = par_centroid[v], level++)
{
if (id[v] == timer)
mn = min(mn, ans[v] + dpar[u][level]);
}
return mn;
}
int n;
void solve()
{
timer = 0;
first_dfs(1, 0); // calculate h, par for lca
// RMQ for lca
{
int lg = __lg(n);
for (int i = 1; i <= lg; i++)
{
for (int j = 1; j <= n; j++)
{
par[j][i] = par[par[j][i - 1]][i - 1];
d[j][i] = d[j][i - 1] + d[par[j][i - 1]][i - 1];
}
}
}
build(1, 0);
for (int i = 1; i <= n; i++)
{
for (int v = i, level = 0; v; v = par_centroid[v], level++)
{
dpar[i][level] = get_dis(i, v);
}
}
}
void Init(int N, int A[], int B[], int D[])
{
n = N;
for (int i = 0; i < n - 1; i++)
{
A[i]++;
B[i]++;
int u = A[i], v = B[i], w = D[i];
G[u].emplace_back(v, w);
G[v].emplace_back(u, w);
}
solve();
}
long long Query(int S, int X[], int T, int Y[])
{
timer++;
int s = S, t = T;
for (int i = 0; i < s; i++)
{
modify(X[i] + 1);
}
long long ans = inf;
for (int i = 0; i < t; i++)
{
ans = min(ans, query(Y[i] + 1));
}
// cout << "ANSWER ";
return ans;
}
