#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1, LOG = 20;
int n, st[2 * N][LOG], pos[N], h[N], num[N], tail[N], cnt = 0, timeDfs = 0;
long long d[N];
vector<pair<int, int>> adj[N];
vector<int> adj2[N];
void dfs(int u, int p) {
st[++cnt][0] = u;
pos[u] = cnt;
num[u] = ++timeDfs;
for (auto [v, w] : adj[u]) {
if (v == p) continue;
d[v] = d[u] + w;
h[v] = h[u] + 1;
dfs(v, u);
st[++cnt][0] = u;
}
tail[u] = timeDfs;
}
#define minHigh(u, v) (h[u] < h[v] ? u : v)
int lck(int u, int v) {
u = pos[u], v = pos[v];
if (u > v) swap(u, v);
int k = __lg(v - u + 1);
return minHigh(st[u][k], st[v - (1 << k) + 1][k]);
}
void Init(int _N, int A[], int B[], int D[]) {
::n = _N;
for (int i = 0; i < n - 1; i++) {
A[i]++, B[i]++;
adj[A[i]].push_back({ B[i], D[i] });
adj[B[i]].push_back({ A[i], D[i] });
}
dfs(1, 1);
for (int k = 1; 1 << k <= cnt; k++)
for (int i = 1; i + (1 << k) - 1 <= cnt; i++) st[i][k] = minHigh(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
}
const long long inf = 1e18;
long long res = 0, dp[N][2];
int x[N], mark[N], col[N], cur = 0, sz = 0;
void process(int u) {
if (col[u] == 1) dp[u][0] = 0;
if (col[u] == 2) dp[u][1] = 0;
for (int v : adj2[u]) {
process(v);
res = min(res, min(dp[u][0] + dp[v][1], dp[u][1] + dp[v][0]) + d[v] - d[u]);
dp[u][0] = min(dp[u][0], dp[v][0] + d[v] - d[u]);
dp[u][1] = min(dp[u][1], dp[v][1] + d[v] - d[u]);
}
}
long long Query(int S, int X[], int T, int Y[]) {
cur++;
sz = 0;
for (int i = 0; i < S; i++) {
X[i]++;
mark[X[i]] = cur;
col[X[i]] = 1;
x[sz++] = X[i];
}
for (int i = 0; i < T; i++) {
Y[i]++;
mark[Y[i]] = cur;
col[Y[i]] = 2;
x[sz++] = Y[i];
}
sort(x, x + sz, [&](int u, int v) { return num[u] < num[v]; });
for (int i = 0; i < sz - 1; i++) {
int u = lck(x[i], x[i + 1]);
if (mark[u] != cur) {
mark[u] = cur;
x[sz++] = u;
}
}
sort(x, x + sz, [&](int u, int v) { return num[u] < num[v]; });
for (int i = 0; i < sz; i++) adj2[x[i]].clear(), dp[x[i]][0] = dp[x[i]][1] = inf;
stack<int> s;
s.push(x[0]);
for (int i = 1; i < sz; i++) {
while (tail[s.top()] < num[x[i]]) s.pop();
adj2[s.top()].push_back(x[i]);
s.push(x[i]);
}
res = inf;
process(x[0]);
for (int i = 0; i < S; i++) col[X[i]] = 0;
for (int i = 0; i < T; i++) col[Y[i]] = 0;
return res;
}
// #define MAX_N 500000
// #define MAX_Q 100000
// #define MAX_SUM_ST 1000000
// #define MAX_VALUE 1000000000
// static int _N, Q;
// static int A[MAX_N], B[MAX_N], D[MAX_N];
// static int S[MAX_N];
// static int T[MAX_N];
// static int X[MAX_SUM_ST];
// static int Y[MAX_SUM_ST];
// static int Qx[MAX_N];
// static int Qy[MAX_N];
// int main() {
// ios::sync_with_stdio(0);
// cin.tie(0);
// int i, j, k;
// int STop, TTop;
// scanf("%d%d", &_N, &Q);
// for (i = 0; i < _N - 1; ++i) {
// scanf("%d", &A[i]);
// scanf("%d", &B[i]);
// scanf("%d", &D[i]);
// }
// STop = 0;
// TTop = 0;
// for (j = 0; j < Q; ++j) {
// scanf("%d%d", &S[j], &T[j]);
// for (k = 0; k < S[j]; ++k, ++STop) {
// scanf("%d", &X[STop]);
// }
// for (k = 0; k < T[j]; ++k, ++TTop) {
// scanf("%d", &Y[TTop]);
// }
// }
// STop = 0;
// TTop = 0;
// Init(_N, A, B, D);
// for (j = 0; j < Q; ++j) {
// for (k = 0; k < S[j]; k++) {
// Qx[k] = X[STop++];
// }
// for (k = 0; k < T[j]; k++) {
// Qy[k] = Y[TTop++];
// }
// printf("%lld\n", Query(S[j], Qx, T[j], Qy));
// }
// }
