/* Bismillahir Rahmanir Rahim */
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef pair <int, long long> pii;
const int N = 500005;
const long long oo = 1e18;
vector <pii> g[N];
int n;
int tot;
int sub[N];
int anc[N];
int vis[N];
long long mn[N];
vector <long long> pre[N];
stack <int> rem;
void dfs0(int at, int par){
++tot;
sub[at] = 1;
for(auto u : g[at]){
if(vis[u.first] || u.first == par) continue;
dfs0(u.first, at);
sub[at] += sub[u.first];
}
}
int get(int at, int par){
for(auto u : g[at]){
if(vis[u.first] || u.first == par) continue;
if(sub[u.first] > tot / 2) return get(u.first, at);
}
return at;
}
void get_dis(int at, int par, long long dis){
pre[at].push_back(dis);
for(auto u : g[at]){
if(vis[u.first] || u.first == par) continue;
get_dis(u.first, at, dis + u.second);
}
}
void decompose(int at, int par){
tot = 0;
dfs0(at, at);
int cen = get(at, at);
vis[cen] = 1;
if(par) anc[cen] = par;
get_dis(cen, cen, 0);
for(auto u : g[cen]){
if(vis[u.first]) continue;
decompose(u.first, cen);
}
}
void update(int from){
int cur = from;
for(auto u : pre[from]){
mn[cur] = min(mn[cur], u);
rem.push(cur);
cur = anc[cur];
}
}
long long query(int from){
int cur = from;
long long ret = oo;
for(auto u : pre[from]){
ret = min(ret, mn[cur] + u);
cur = anc[cur];
}
return ret;
}
void reset(){
while(!rem.empty()){
mn[rem.top()] = oo;
rem.pop();
}
}
long long Query(int S, int X[], int T, int Y[]){
reset();
for(int i = 0; i < S; ++i){
update(X[i] + 1);
}
long long ret = oo;
for(int i = 0; i < T; ++i){
ret = min(ret, query(Y[i] + 1));
}
return ret;
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(int i = 0; i < N - 1; ++i){
g[A[i] + 1].push_back({B[i] + 1, D[i]});
g[B[i] + 1].push_back({A[i] + 1, D[i]});
}
decompose(1, 0);
for(int i = 1; i <= n; ++i) mn[i] = oo;
for(int i = 1; i <= n; ++i){
reverse(pre[i].begin(), pre[i].end());
}
}
