#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
const int MAX = 5e5 + 10;
vector<int> adj[MAX], cost[MAX];
int lvl[MAX], sub[MAX], p[MAX], vis[MAX];
ll d[20][MAX], ans[MAX];
void calc(int u, int par) { sub[u] = 1;
for(int v : adj[u]) if(v - par && !vis[v])
calc(v, u), sub[u] += sub[v];
}
int centroid(int u, int par, int r) {
for(int v : adj[u]) if(v - par && !vis[v])
if(sub[v] > r) return centroid(v, u, r);
return u;
}
void dfs(int l, int u, int par, int pcost) {
if(par + 1) d[l][u] = d[l][par] + pcost;
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i], c = cost[u][i];
if(v == par || vis[v]) continue;
dfs(l, v, u, c);
}
}
void decompose(int u, int par) {
calc(u, -1);
int c = centroid(u, -1, sub[u] >> 1);
vis[c] = 1, p[c] = par;
if(par + 1) lvl[c] = lvl[par] + 1;
dfs(lvl[c], c, -1, 0);
for(int v : adj[c]) if(v - par && !vis[v])
decompose(v, c);
}
void update(int u) {
for(int v = u; v + 1; v = p[v])
ans[v] = min(ans[v], d[lvl[v]][u]);
}
ll query(int u) {
ll ret = 1e18;
for(int v = u; v + 1; v = p[v])
ret = min(ret, ans[v] + d[lvl[v]][u]);
return ret;
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N - 1; i++) {
int u = A[i], v = B[i], c = D[i];
adj[u].push_back(v);
adj[v].push_back(u);
cost[u].push_back(c);
cost[v].push_back(c);
}
for(int i = 0; i < N; i++)
ans[i] = 1e18;
decompose(0, -1);
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i = 0; i < S; i++)
update(X[i]);
ll ret = 1e18;
for(int i = 0; i < T; i++)
ret = min(ret, query(Y[i]));
for(int i = 0; i < S; i++) {
for(int v = X[i]; v + 1; v = p[v])
ans[v] = 1e18;
} return ret;
}
