#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 5e5+100;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
vector<pair<int,ll>>g[maxn];
int n, subt[maxn], vis[maxn], par[maxn], lvl[maxn];
ll dist[maxn][20], best[maxn];
int dfs(int u,int p,int lvl,int d){
if(lvl!=-1)dist[u][lvl] = dist[p][lvl]+d;
subt[u] = 1;
for(auto [v,w]:g[u]){
if(v==p||vis[v])continue;
subt[u] += dfs(v,u,lvl,w);
}
return subt[u];
}
int find_centroid(int u,int p,int tam){
for(auto [v,d]:g[u]){
if(vis[v]||v==p)continue;
if(subt[v]*2>tam)return find_centroid(v,u,tam);
}
return u;
}
void centroid_decomposition(int u=1,int p=-1,int w=0){
int c = find_centroid(u,p, dfs(u,p,p==-1?-1:lvl[p],w) );
vis[c] = 1, par[c] = p;
if(p!=-1)lvl[c] = lvl[p] + 1;
for(auto [v,w]:g[c]){
if(vis[v])continue;
centroid_decomposition(v,c,w);
}
}
void Init(int N,int a[],int b[],int d[]) {
n = N;
for(int i=0;i<n-1;++i){
++a[i], ++b[i];
g[a[i]].pb({b[i],d[i]});
g[b[i]].pb({a[i],d[i]});
}
centroid_decomposition();
for(int i=1;i<=n;++i)best[i] = 1e18;
}
ll distance(int u,int v){
int su = u, sv = v;
if(lvl[u]<lvl[v])swap(u,v), swap(su,sv);
while(lvl[u]!=lvl[v])u = par[u];
while(u!=v)u = par[u], v = par[v];
return dist[su][lvl[u]] + dist[sv][lvl[u]];
}
void update(int u, bool type){
int cur = u;
while(cur!=-1){
if(type)ckmin(best[cur],dist[u][lvl[cur]]);
else best[cur] = 1e18;
cur = par[cur];
}
}
ll query(int u){
ll resp = best[u];
int cur = par[u];
while(cur!=-1){
ckmin(resp,best[cur]+distance(u,cur));
cur = par[cur];
}
return resp;
}
long long Query(int S,int X[], int T,int Y[]) {
for(int i=0;i<T;++i){
update(Y[i]+1,1);
}
ll ans = 1e18;
for(int i=0;i<S;++i){
ckmin(ans,query(X[i]+1));
}
for(int i=0;i<T;++i)update(Y[i]+1,0);
return ans;
}
// int main(){
// int n,q;cin>>n>>q;
// vector<int>a,b,d;
// for(int i=0;i<n-1;++i){
// int x,y,z;cin>>x>>y>>z;
// a.pb(x), b.pb(y), d.pb(z);
// }
// vector<vector<int>>s, t;
// for(int i=0;i<q;++i){
// vector<int>sc, tc;
// int x,y;cin>>x>>y;
// for(int j=0;j<x;++j){
// int z;cin>>z;
// sc.pb(z);
// }
// for(int j=0;j<y;++j){
// int z;cin>>z;
// tc.pb(z);
// }
// s.pb(sc), t.pb(tc);
// }
// Init(n,a,b,d);
// for(int i=0;i<q;++i){
// cout<<Query(sz(s[i]),s[i],sz(t[i]),t[i])<<endl;
// }
// }
