#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define lc (i << 1)
#define rc (i << 1 | 1)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 5e5 + 5, LN = 19, MOD = 1e9 + 7, INF = 0x3f3f3f3f, BSZ = 320;
vector<pii> g[MN];
int sz[MN], par[MN], lvl[MN];
ll down[LN][MN]; // dis from a centroid at lvl j, to a node i
bool vis[MN];
ll mn[MN]; // mn dis from centroid i, to any factory of first kind in children
int qid[MN], id = 1;
int get_sz(int u, int p) {
sz[u] = 1;
for (pii e : g[u]) if (e.first != p && !vis[e.first])
sz[u] += get_sz(e.first, u);
return sz[u];
}
int centroid(int u, int p, int s) {
for (pii e : g[u]) if (e.first != p && !vis[e.first] && sz[e.first] > s / 2)
return centroid(e.first, u, s);
return u;
}
void dfs(int u, int p, ll dis, int d) {
down[d][u] = dis;
for (pii e : g[u]) if (e.first != p && !vis[e.first])
dfs(e.first, u, dis + e.second, d);
}
void go(int u, int p, int d) {
int s = get_sz(u, -1);
int c = centroid(u, -1, s);
par[c] = p;
lvl[c] = d;
dfs(c, -1, 0, d);
vis[c] = true;
for (pii e : g[c]) {
if (!vis[e.first]) {
go(e.first, c, d + 1);
}
}
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
int u = A[i], v = B[i], w = D[i];
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
memset(down, 0x3f, sizeof(down));
go(0, -1, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i = 0; i < S; i++) {
int cur = X[i];
while (cur != -1) {
if (qid[cur] != id) qid[cur] = id, mn[cur] = down[lvl[cur]][X[i]];
else mn[cur] = min(mn[cur], down[lvl[cur]][X[i]]);
cur = par[cur];
}
}
ll ret = LLONG_MAX;
for (int i = 0; i < T; i++) {
int cur = Y[i];
while (cur != -1) {
if (qid[cur] == id) ret = min(ret, mn[cur] + down[lvl[cur]][Y[i]]);
cur = par[cur];
}
}
id++;
return ret;
}
/*
int main() {
int N, Q;
cin >> N >> Q;
int a[N + 1], b[N + 1], d[N + 1];
for (int i = 0; i < N - 1; i++) cin >> a[i] >> b[i] >> d[i];
Init(N, a, b, d);
for (int i = 0; i < Q; i++) {
int s, t;
cin >> s >> t;
int x[s + 1], y[t + 1];
for (int j = 0; j < s; j++) cin >> x[j];
for (int j = 0; j < t; j++) cin >> y[j];
cout << Query(s, x, t, y) << '\n';
}
return 0;
}
*/
