#include "factories.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include "bits/stdc++.h"
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define int long long
#define sz(x) (int)x.size()
#define i32 int32_t
template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }
const int MAXN = 5e5+5;
const int mod = 1e9+7;
const int inf = 1e18;
vector<pii> edges[MAXN];
int n, tin[MAXN], tout[MAXN], t, lg[2*MAXN], dep[MAXN];
int st[MAXN*2][20];
vector<int> ss;
void dfs(int u, int p = -1){
ss.pb(dep[u]);
tin[u] = sz(ss)-1;
for(auto x : edges[u]){
if(x.ff == p) continue;
dep[x.ff] = dep[u] + x.ss;
dfs(x.ff, u), ss.pb(dep[u]);
} tout[u] = sz(ss)-1;
}
bool par(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }
int find_lca(int a, int b){
if(par(a, b)) return dep[b] - dep[a];
if(par(b, a)) return dep[a] - dep[b];
if(tin[a] > tout[b]) swap(a, b);
int l = tout[a], r = tin[b], llg = lg[r-l+1];
int dis = min(st[l][llg], st[r-(1<<llg)+1][llg]);
return dep[a] + dep[b] - dis * 2ll;
}
void Init(i32 N, i32 a[], i32 b[], i32 d[]) {
n = N;
for(int i=0;i<n-1;i++){ a[i]++, b[i]++;
edges[a[i]].pb({b[i], d[i]}), edges[b[i]].pb({a[i], d[i]});
} dfs(1);
lg[1] = 0;
for(int i=2;i<2*MAXN;i++) lg[i] = lg[i>>1]+1;
for(int i=0;i<sz(ss);i++) st[i][0] = ss[i];
for(int j=1;j<20;j++){
for(int i=0;i<sz(ss);i++){
if(i + (1<<(j - 1)) < sz(ss)) st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
else st[i][j] = st[i][j-1];
}
}
}
int dis[MAXN];
int Query(i32 s, i32 x[], i32 t, i32 y[]) {
for(int i=0;i<s;i++) x[i]++;
for(int i=0;i<t;i++) y[i]++;
if(n > 5000){
int res = inf;
for(int i=0;i<s;i++){
for(int j=0;j<t;j++){
int a = x[i], b = y[j];
umin(res, find_lca(a, b));
}
} return res;
} else {
int res = inf;
for(int i=1;i<=n;i++) dis[i] = inf;
queue<int> qq;
for(int i=0;i<s;i++) qq.push(x[i]), dis[x[i]] = 0;
while(!qq.empty()){
int u = qq.front(); qq.pop();
for(auto x : edges[u]) if(umin(dis[x.ff], dis[u] + x.ss)) qq.push(x.ff);
}
for(int i=0;i<t;i++) umin(res, dis[y[i]]);
return res;
}
}
