#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#include "factories.h"
const int n = 5e5 + 10;
const long long inf = 1e18;
const int LOG = 20;
using namespace std;
vector<pair<int,int>>g[n];
int up[n][LOG],in[n],out[n],timer = 0,siz[n],nxt[n];
long long dist[n],ans[n];
bool was[n];
void DFS(int x,int par) {
siz[x] = 1;
for(auto X : g[x]) {
if(!was[X.F] && X.F != par) {
DFS(X.F,x);
siz[x] += siz[X.F];
}
}
}
int Find(int u,int par,int q) {
for(auto X : g[u]) {
if(X.F != par && !was[X.F] && siz[X.F] > q / 2) return Find(X.F,u,q);
}
return u;
}
void Find_centroid(int u,int par) {
DFS(u,-1);
u = Find(u,-1,siz[u]);
was[u] = true;
nxt[u] = par;
for(auto X : g[u]) {
if(!was[X.F]) Find_centroid(X.F,u);
}
}
bool In(int u,int v) {
return (in[u] <= in[v] && out[u] >= out[v]);
}
int LCA(int u,int v) {
if(In(u,v)) return u;
if(In(v,u)) return v;
for(int j = LOG - 1; j >= 0; j--) {
if(up[u][j] >= 0 && !In(up[u][j],v)) u = up[u][j];
}
return up[u][0];
}
long long Dist(int u,int v) {
return dist[u] + dist[v] - 2 * dist[LCA(u,v)];
}
void Add(int x) {
int y = x;
while(x >= 0) {
ans[x] = min(ans[x],Dist(x,y));
x = nxt[x];
}
}
void Rem(int x) {
int y = x;
while(x >= 0) {
ans[x] = inf;
x = nxt[x];
}
}
long long Get(int x) {
long long y = x,res = inf;
while(x >= 0) {
res = min(res,ans[x] + Dist(x,y));
x = nxt[x];
}
return res;
}
void dfs(int x,int par) {
in[x] = ++timer;
up[x][0] = par;
for(int j = 1; j < LOG; j++) up[x][j] = up[up[x][j - 1]][j - 1];
for(auto X : g[x]) {
if(X.F != par) {
dist[X.F] = dist[x] + X.S;
dfs(X.F,x);
}
}
out[x] = timer;
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N - 1; i++) {
g[A[i]].pb({B[i],D[i]});
g[B[i]].pb({A[i],D[i]});
}
for(int i = 0; i < N; i++) for(int j = 0; j < LOG; j++) up[i][j] = -1;
dfs(0,0);
Find_centroid(0,-1);
for(int i = 0; i < N; i++) ans[i] = inf;
}
long long Query(int S, int X[], int T, int Y[]) {
long long res = inf;
for(int i = 0; i < S; i++) Add(X[i]);
for(int i = 0; i < T; i++) res = min(res,Get(Y[i]));
for(int i = 0; i < S; i++) Rem(X[i]);
return res;
}
/*
7 3
0 1 4
1 2 4
2 3 5
2 4 6
4 5 5
1 6 3
2 2
0 6
3 4
3 2
0 1 3
4 6
1 1
2
5
12
3
11
*/
