#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
/*************** LCA ******************/
const int N = 5 * 1e5 + 1 ;
const int Log = 21;
const ll inf = 1e18 ;
int n ;
int P[N][Log], L[N] ;
ll cost[N];
vector < pair < int , int > > G[N];
void dfs(int u, int p, int d , ll w) {
P[u][0] = p ;
L[u] = d ;
cost[u] = w;
for(auto e : G[u]) {
int v = e.first , c = e.second ;
if(v == p)
continue ;
dfs(v, u, d + 1, w + c);
}
}
void dp() {
for(int i = 0 ; i < n ; i++)
for(int j = 1 ; (1 << j) < n ; j++)
P[i][j] = -1 ;
for(int j = 1 ; (1 << j) < n ; j++)
for(int i = 0 ; i < n ; i++)
if(P[i][j - 1] != -1)
P[i][j] = P[P[i][j - 1]][j - 1] ;
}
int lca(int u, int v) {
if(L[u] < L[v])
swap(u, v);
int i, log ;
for(log = 1 ; (1 << log) <= L[u] ; log++);
log -- ;
for(i = log ; i >= 0 ; i--) {
if(L[u] - (1 << i) >= L[v])
u = P[u][i] ;
}
if(u == v)
return u ;
for(i = log ; i >= 0 ; i--) {
if(P[u][i] != -1 && P[u][i] != P[v][i])
u = P[u][i], v = P[v][i] ;
}
return P[u][0];
}
ll dist(int u, int v) {
return cost[u] + cost[v] - 2 * cost[lca(u, v)];
}
/*************** Centroid ******************/
int sub[N], par[N];
bool blocked[N];
vector < pair < int , int > > tree[N];
void get_size(int u, int p) {
par[u] = p ;
sub[u] = 1 ;
for(auto e : G[u]) {
int v = e.first ;
if(v == p || blocked[v])
continue ;
get_size(v, u);
sub[u] += sub[v];
}
}
int get_centroid(int src) {
get_size(src, src);
int centroid = src, best = sub[src] ;
queue < int > Q ;
Q.emplace(src);
while(!Q.empty()) {
int u = Q.front();
Q.pop();
int size = sub[src] - sub[u];
for(auto e : G[u]) {
int v = e.first;
if(v == par[u] || blocked[v])
continue ;
Q.emplace(v);
size = max(size, sub[v]);
}
if(best > size) {
best = size;
centroid = u ;
}
}
blocked[centroid] = true;
for(auto e : G[centroid]) {
int v = e.first ;
if(blocked[v]) continue ;
int child = get_centroid(v);
tree[centroid].push_back({child , 0});
tree[child].push_back({centroid , 0});
}
return centroid ;
}
ll ans[N];
vector < ll > dis[N];
void update(int u){
int v = u ;
int i = 0 ;
while(true){
if(ans[v] != -1) ans[v] = min(ans[v] , dis[u][i]);
else ans[v] = dis[u][i] ;
if(v == par[v]) break ;
v = par[v];
i++ ;
}
}
ll query(int u){
int v = u ;
ll ret = inf ;
int i = 0 ;
while(true){
if(ans[v] != -1) ret = min(ret , ans[v] + dis[u][i]);
if(v == par[v]) break ;
v = par[v];
i++ ;
}
return ret;
}
ll Query(int S , int X[] , int T , int Y[]){
memset(ans , -1 , sizeof ans);
for(int i = 0 ; i < T ; i++){
update(Y[i]);
}
ll ret = inf ;
for(int i = 0 ; i < S ; i++){
ret = min(ret, query(X[i]));
}
return ret;
}
void Init(int N , int A[] , int B[] , int D[]){
n = N ;
for(int i = 0 ; i < n - 1 ; i++){
int u = A[i] , v = B[i] , w = D[i];
G[u].push_back({v , w});
G[v].push_back({u , w});
}
dfs(0 , -1 , 0 , 0);
dp();
int root = get_centroid(0);
memset(blocked , 0 , sizeof blocked);
swap(tree , G);
get_size(root , root);
for(int i = 0 ; i < n ; i++){
int v = i ;
while(true){
dis[i].push_back(dist(v , i));
if(v == par[v]) break ;
v = par[v];
}
}
}
