#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5+4;
const ll inf = 1e18;
struct Cd{
vector<pair<int,int>> adj[N];
int sz[N],up[N],h[N],vis[N];
ll dis[N][19],val[N];
int find(int u,int p,int Sz){
int val = 0,x = 0; sz[u] = 1;
for (auto [v, w] : adj[u]) if (v != p && !vis[v]){
x ^= find(v, u, Sz); sz[u] += sz[v];
val = max(val, sz[v]);
}
if (max(val, Sz-sz[u]) <= Sz/2) up[x = u] = p;
return x;
}
void dfs(int u,int p,int H){
for (auto [v, w] : adj[u]) if (v != p && !vis[v]){
dis[v][H] = dis[u][H] + w;
dfs(v, u, H);
}
}
void build(int u,int p,int Sz){
u = find(u, -1, Sz);
if (up[u] != -1) sz[up[u]] = Sz-sz[u];
vis[u] = 1, h[u] = h[p]+1, up[u] = p, val[u] = inf;
dfs(u, -1, h[u]);
for (auto [v, w] : adj[u]) if (!vis[v])
build(v, u, sz[v]);
}
void upd(int u,bool f){
for (int v=u; v; v=up[v]){
if (f) val[v] = min(val[v], dis[u][h[v]]);
else val[v] = inf;
}
}
ll que(int u){
ll ans = inf;
for (int v=u; v; v=up[v]) ans = min(ans, dis[u][h[v]] + val[v]);
return ans;
}
} d;
void Init(int n, int A[], int B[], int D[]) {
for (int i=0; i<n-1; i++){
d.adj[++A[i]].push_back({++B[i], D[i]});
d.adj[B[i]].push_back({A[i], D[i]});
}
d.h[0] = -1;
d.build(1, 0, n);
}
ll Query(int S, int X[], int T, int Y[]) {
for (int i=0; i<S; i++) d.upd(++X[i], 1);
ll ans = inf;
for (int i=0; i<T; i++) ans = min(ans, d.que(++Y[i]));
for (int i=0; i<S; i++) d.upd(X[i], 0);
return ans;
}
/*
int n,q,S,T;
int A[N],B[N],D[N],X[N],Y[N];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> q;
for (int i=0; i+1<n; i++) cin >> A[i] >> B[i] >> D[i];
Init(n, A, B, D);
while (q--){
cin >> S >> T;
for (int i=0; i<S; i++) cin >> X[i];
for (int i=0; i<T; i++) cin >> Y[i];
cout << Query(S, X, T, Y) << "\n";
}
return 0;
}
*/
