#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//#define int ll
using P = pair<int, int>;
using PL = pair<ll, int>;
#define all(x) x.begin(), x.end()
#define rep(i, l, n) for (int i = l; i < (n); ++i)
#define sz(x) (int)x.size()
const char nl = '\n';
const ll NMAX = 5e5+10;
const ll inf = NMAX*(ll)1e9;
const int LOG = 20;
vector<P> g[NMAX];
ll d[NMAX];
int specific[NMAX], NN;
bool removed[NMAX];
int sz[NMAX], p[NMAX];
int L[NMAX][20], dep[NMAX];
ll ss[NMAX];
vector<int> euler;
int fp[NMAX], ptr = 0;
vector<int> logn;
vector<int> depa;
vector<vector<int>> dp;
//ll LS[NMAX][20];
void build_sparse_table(int n) {
dp.resize(n);
rep(i, 0, n)
dp[i].resize(log2(n)+1, -1);
rep(i, 0, n)
dp[i][0] = i;
rep(l, 1, log2(n)+1) {
int x = 1<<(l-1);
rep(i, 0, n)
if (dp[i][l-1] != -1 && i+x < n && dp[i+x][l-1] != -1)
dp[i][l] = (depa[dp[i][l-1]] < depa[dp[i+x][l-1]]?dp[i][l-1]:dp[i+x][l-1]);
else break;
}
}
int query(int l, int r) {
int len = r-l+1;
int dx = logn[len];
if (l == r)return l;
//cout << l << " " << r << nl;
//cout << dx << nl;
if (depa[dp[l][dx]] < depa[dp[r-(1<<dx)+1][dx]])return dp[l][dx];
return dp[r-(1<<dx)+1][dx];
}
void dfs(int node = 0, int par = -1, int sum = 0) {
L[node][0] = par;
rep(i, 1, LOG) {
if (L[node][i-1] == -1)break;
L[node][i] = L[L[node][i-1]][i-1];
//ss[node] = ]
//LS[node][i] = LS[node][i-1]+LS[L[node][i-1]][i-1];
}
if (fp[node] == -1)fp[node] = ptr;
euler.push_back(node);
ptr += 1;
for (auto [child, w]: g[node]) {
if (child == par)continue;
dep[child] = dep[node]+1;
//LS[child][0] = w;
ss[child] = ss[node]+w;
dfs(child, node, sum+w);
ptr += 1;
euler.push_back(node);
}
}
int get_subtree_size(int node, int par =-1) {
sz[node] = 1;
for (auto [child, w]: g[node]) {
if (child == par || removed[child])continue;
sz[node] += get_subtree_size(child, node);
}
return sz[node];
}
int get_centroid(int node, int tree_size, int par = -1) {
for (auto [child, w]: g[node]) {
if (child == par || removed[child])continue;
if (sz[child]*2>tree_size)return get_centroid(child, tree_size, node);
}
return node;
}
void build_centroid_decomp(int node = 0, int par = -1, int lev = 0) {
int centroid = get_centroid(node, get_subtree_size(node));
removed[centroid] = 1; p[centroid] = par;
//cout << centroid << " " << lev << nl;
for (auto [child, w]: g[centroid]) {
//if (node == 2)cout << child << nl;
if (removed[child])continue;
build_centroid_decomp(child, centroid, lev+1);
}
//cout << endl;
}
void Init(int N, int A[], int B[], int D[]) {
memset(L, -1, sizeof L);
memset(fp, -1, sizeof fp);
NN = N;
rep(i, 0, N-1)
g[A[i]].push_back({B[i], D[i]}),
g[B[i]].push_back({A[i], D[i]});
rep(i, 0, N)d[i] = inf;
//cout << g[2][0].first << nl;
build_centroid_decomp();
dfs();
for (auto x: euler) {
depa.push_back(dep[x]);
//cout << dep[x] << " ";
}
//cout << nl;
build_sparse_table(sz(depa));
logn.resize(sz(depa)+10);
logn[0] = -1;
rep(i, 1, sz(logn))logn[i] = logn[i/2]+1;
}
ll dist(int x, int y) {
ll sum = ss[x]+ss[y];
if (x == y)return 0;
if (fp[x] > fp[y])swap(x, y);
//cout << fp[x] << " " << fp[y] << nl;
//return ss[euler[query(fp[x], fp[y])]];
//cout << euler[que]
//cout << ss[x] << " " << ss[y] << " " <<euler[query(fp[x], fp[y])] << nl;
//return 0;e
//cout << sum << nl;
return sum-2*ss[euler[query(fp[x], fp[y])]];
//if(dep[y]>dep[x])swap(x, y);
//for (int i = 19; i >= 0; --i)
//if (L[x][i] != -1 && dep[L[x][i]] >= dep[y]) {
//x = L[x][i];
//}
//if (x == y)return sum-2ll*ss[x];
//for (int i = 19; i >= 0; i--)
//if (L[x][i] != L[y][i]) {
//x = L[x][i], y = L[y][i];
//}
//return sum-2*ss[L[x][0]];
}
long long Query(int S, int X[], int T, int Y[]) {
rep(i, 0, S) {
int x = X[i];
while (x != -1) {
d[x] = min(d[x], dist(x, X[i]));
//cout << X[i] << " " << x << " " << d[x] << nl;
x = p[x];
}
}
ll res = inf;
rep(i, 0, T) {
int y = Y[i];
while (y != -1) {
res = min(res, d[y]+dist(y, Y[i])),
//cout << Y[i] << " " << y << " " << dist(y, Y[i]) << nl;
y = p[y];
}
}
rep(i, 0, S) {
int x = X[i];
while (x != -1)
d[x] = inf, x = p[x];
}
return res;
}
//int32_t main() {
//int n, q; cin >> n >> q;
//int A[n-1], B[n-1], D[n-1];
//rep(i, 0, n-1) {
//cin >> A[i] >> B[i] >> D[i];
//}
//Init(n, A, B, D);
//rep(i, 0, q) {
//int s, t; cin >> s >> t;
//int x[s], y[t];
//rep(j, 0, s)cin >> x[j];
//rep(j, 0, t)cin >> y[j];
//cout << Query(s, x, t, y) << nl;
//}
//}
