#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], LS[NMAX][20], dep[NMAX];
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];
LS[node][i] = LS[node][i-1]+LS[L[node][i-1]][i-1];
}
for (auto [child, w]: g[node]) {
if (child == par)continue;
dep[child] = dep[node]+1;
LS[child][0] = w;
dfs(child, node, sum+w);
}
}
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 centroid = get_centroid(node, get_subtree_size(node));
removed[centroid] = 1; p[centroid] = par;
for (auto [child, w]: g[node]) {
if (removed[child])continue;
build_centroid_decomp(child, centroid);
}
}
void Init(int N, int A[], int B[], int D[]) {
memset(L, -1, sizeof L);
NN = N;
rep(i, 0, N)d[i] = inf;
rep(i, 0, N-1)
g[A[i]].push_back({B[i], D[i]}),
g[B[i]].push_back({A[i], D[i]});
build_centroid_decomp();
dfs();
}
ll dist(int x, int y) {
ll sum = 0;
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]) {
sum += LS[x][i];
x = L[x][i];
}
if (x == y)return sum;
for (int i = 19; i >= 0; i--)
if (L[x][i] != L[y][i]) {
sum += LS[x][i]+LS[y][i];
x = L[x][i], y = L[y][i];
}
return sum+LS[x][0]+LS[y][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])),
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])),
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;
//}
//}
