#include <bits/stdc++.h>
#include "factories.h"
//#define int long long
#define debug cout << "ok\n";
#define SQR(x) (1LL * ((x) * (x)))
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pli pair<ll,int>
#define vi vector<int>
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int ui;
using namespace std;
const int M = 1e9 + 7;
const int INF = 1e9 + 7;
const ll INFLL = (ll)2e18 + 7LL;
const ld PI = acos(-1);
const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
template<class _, class __>
bool minimize(_ &x, const __ y){
if(x > y){
x = y;
return true;
} else return false;
}
template<class _, class __>
bool maximize(_ &x, const __ y){
if(x < y){
x = y;
return true;
} else return false;
}
template<class _,class __>
void Add(_ &x, const __ y) {
x += y;
if (x >= M) {
x -= M;
}
return;
}
template<class _,class __>
void Diff(_ &x, const __ y) {
x -= y;
if (x < 0) {
x += M;
}
return;
}
//--------------------------------------------------------------
const int MaxN = 1e6+7;
const int Log = 20;
int sz[MaxN],Arr[MaxN],Tin[MaxN],Tout[MaxN],Left[MaxN][Log],Right[MaxN][Log],z[MaxN],cnt = 0,f[MaxN],par[MaxN],h[MaxN];
ll dist[MaxN];
bool isCT[MaxN];
vector<pii> a[MaxN];
void dfs(int u,int p) {
sz[u] = 1;
for (pii e : a[u]) {
int v = e.fi;
if (isCT[v] | v == p) continue;
dfs(v,u);
sz[u] += sz[v];
}
}
int GetCen(int u,int p,int r) {
for (pii e : a[u]) {
int v = e.fi;
if (isCT[v] || v == p) continue;
if (sz[v] * 2 >= sz[r]) return GetCen(v,u,r);
}
return u;
}
void Centroid(int u,int p) {
dfs(u,-1);
u = GetCen(u,-1,u);
isCT[u] = true;
if (p >= 0) par[u] = p;
for (pii e : a[u]) {
int v = e.fi;
if (!isCT[v]) {
Centroid(v,u);
}
}
}
void dfsss(int u,int p) {
Arr[++cnt] = u;
for (pii e : a[u]) {
int v = e.fi;
int w = e.se;
if (v == p) continue;
h[v] = h[u] + 1;
dist[v] = dist[u] + w;
dfsss(v,u);
Arr[++cnt] = u;
}
}
int LCA(int u,int v) {
if (Tin[u] > Tin[v]) swap(u,v);
if (Tin[u] <= Tin[v] && Tout[v] <= Tout[u]) return u;
u = Tout[u];
v = Tin[v];
int tmp = z[v - u];
if (h[Right[u][tmp]] < h[Left[v][tmp]]) return Right[u][tmp];
else return Left[v][tmp];
}
ll Dist(int u,int v) {
// cout << u << ' ' << v << ' ' << LCA(u,v) << '\n';
return dist[u] + dist[v] - 2 * dist[LCA(u,v)];
}
void Init(int N,int A[],int B[],int D[]) {
for (int i=1;i<N;i++) A[i-1]++,B[i-1]++;
for (int i=1;i<N;i++) {
int u = A[i-1];
int v = B[i-1];
int w = D[i-1];
a[u].pb(mp(v,w));
a[v].pb(mp(u,w));
}
Centroid(1,-1);
memset(f,0x3f,sizeof(f));
dfsss(1,-1);
// for (int i=1;i<=N;i++) cout << dist[i] << ' '; cout << '\n';
for (int i=1;i<=cnt;i++) Tout[Arr[i]] = i;
for (int i=cnt;i>=1;i--) Tin[Arr[i]] = i;
z[1] = 0;
for (int i=2;i<=cnt;i++) {
z[i] = z[i-1];
while (MASK(z[i]+1) <= i) z[i]++;
}
for (int i=1;i<=cnt;i++) {
Left[i][0] = Right[i][0] = Arr[i];
}
for (int i=1;i<Log;i++) {
for (int j=1;j<=cnt;j++) {
if (j + MASK(i) - 1 <= cnt) {
if (h[Right[j][i-1]] < h[Right[j+MASK(i-1)][i-1]]) Right[j][i] = Right[j][i-1];
else Right[j][i] = Right[j+MASK(i-1)][i-1];
}
if (j - MASK(i) >= 0) {
if (h[Left[j][i-1]] < h[Left[j-MASK(i-1)][i-1]]) Left[j][i] = Left[j][i-1];
else Left[j][i] = Left[j-MASK(i-1)][i-1];
}
}
}
}
void reset(int u) {
while (u) {
f[u] = INFLL;
u = par[u];
}
}
void Upd(int u) {
int v = u;
while (v) {
// cout << u << ' ' << v << ' ' << Dist(u,v) << '\n';
minimize(f[v],Dist(u,v));
v = par[v];
}
}
ll Get(int u) {
ll res = INFLL;
int v = u;
while (v) {
minimize(res,f[v] + Dist(v,u));
v = par[v];
}
return res;
}
long long Query(int S,int X[],int T,int Y[]) {
for (int i=0;i<S;i++) X[i]++;
for (int i=0;i<T;i++) Y[i]++;
for (int i=0;i<S;i++) Upd(X[i]);
ll res = INFLL;
for (int i=0;i<T;i++) minimize(res,Get(Y[i]));
for (int i=0;i<S;i++) reset(X[i]);
return res;
}
//int A_tmp[] = {0,1,2,2,4,1};
//int B_tmp[] = {1,2,3,4,5,6};
//int D_tmp[] = {4,4,5,6,5,3};
//
//int X_tmp[] = {2};
//int Y_tmp[] = {5};
//
//void sol() {
// Init(7,A_tmp,B_tmp,D_tmp);
// cout << Query(1,X_tmp,1,Y_tmp);
//}
//
//signed main() {
//// freopen("test.inp","r",stdin);
//// freopen("test.out","w",stdout);
// FAST
// int t=1;
//// cin >> t;
// while (t--) sol();
//}
