void Init(int N, int A[], int B[], int D[]);
long long Query(int S, int X[], int T, int Y[]);
#include <bits/stdc++.h>
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define fi first
#define se second;
using namespace std;
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
const int MAXN = 5e5 + 5;
const long long inf = 1e18 + 3;
int numNode, numQuery, companyU, companyV, factoryU[MAXN], factoryV[MAXN], sz[MAXN];
bool del[MAXN];
long long best[MAXN];
vector<ii> adj[MAXN];
vector<pair<int, long long> > can[MAXN];
int getSize(int u, int par = 0){
sz[u] = 1;
for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
int v = x.fi, w = x.se;
sz[u] += getSize(v, u);
}
return sz[u];
}
int getCentroid(int sizeU, int u, int par = 0){
for(ii x: adj[u]) if (x.fi != par && !del[x.fi]){
int v = x.fi, w = x.se;
if (sz[v] > (sizeU >> 1)) return getCentroid(sizeU, v, u);
}
return u;
}
void addCan(int u, const int ¢roid, long long dist, int par = 0){
can[u].push_back({centroid, dist});
for(ii x: adj[u]) if (!del[x.fi] && x.fi != par) {
int v = x.fi, w = x.se;
addCan(v, centroid, dist + w, u);
}
}
void decomp(int u = 1){
int centroid = getCentroid(getSize(u), u);
del[centroid] = 1;
for(ii x: adj[centroid]) if (!del[x.fi]) {
int v = x.fi, w = x.se;
addCan(v, centroid, w);
}
for(ii x: adj[centroid]) if (!del[x.fi]){
int v = x.fi, w = x.se;
decomp(v);
}
}
void Init(int N, int A[], int B[], int D[]) {
numNode = N;
int u, v;
for(int i = 0; i < N - 1; i++){
u = A[i]; v = B[i];
u++; v++;
adj[u].push_back({v, D[i]});
adj[v].push_back({u, D[i]});
}
decomp();
for(int u = 1; u <= numNode; u++) can[u].push_back({u, 0});
memset(best, 0x3f, sizeof best);
}
void operation(int u, bool type){
best[u] = (type ? inf: 0);
for(pair<int, long long> x: can[u]){
int centroid = x.fi;
long long dist = x.se;
if (type) best[centroid] = inf;
else minimize(best[centroid], dist);
}
}
long long query(int u){
long long res = inf;
for(pair<int, long long> x: can[u]){
int centroid = x.fi;
long long dist = x.se;
minimize(res, dist + best[centroid]);
}
return res;
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i = 0; i < S; i++) X[i]++;
for(int i = 0; i < T; i++) Y[i]++;
for(int i = 0; i < S; i++) operation(X[i], 0);
long long res = inf;
for(int i = 0; i < T; i++) minimize(res, query(Y[i]));
for(int i = 0; i < S; i++) operation(X[i], 1);
return res;
}
