#include <bits/stdc++.h>
#include "factories.h"
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
#define mkp make_pair
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define eb emplace_back
#define F first
#define S second
const ll ool = 1e18 + 9;
const int NN = 5e5 + 6, C = 20, oo = 1e9 + 9;
int n, tin[NN], tp[NN], timer, lg[NN];
ll lvl[NN], d[NN][2];
pair < int, ll > mn[NN][C + 1];
vector < pair < int, ll > > g[NN];
void dfs(int v, int par) {
tin[v] = ++timer;
mn[0][timer] = mkp(lvl[v], v);
for (auto it : g[v]) {
int to = it.F;
if (to == par) continue;
lvl[to] = lvl[v] + it.S;
dfs(to, v);
mn[0][++timer] = mkp(lvl[v], v);
}
}
ll dfs2(int v, int par) {
d[v][0] = d[v][1] = ool;
ll res = ool;
if (tp[v] == 1) d[v][0] = 0;
if (tp[v] == 2) d[v][1] = 0;
for (auto it : g[v]) {
int to = it.F;
if (to == par) continue;
res = min(res, dfs2(to, v));
d[v][0] = min(d[v][0], d[to][0] + it.S);
d[v][1] = min(d[v][1], d[to][1] + it.S);
}
return min(res, d[v][0] + d[v][1]);
}
int get(int l, int r) {
if (l > r) swap(l, r);
int deg = lg[r - l + 1];
return min(mn[deg][l], mn[deg][r - (1 << deg) + 1]).S;
}
void Init(int _n, int A[], int B[], int D[]) {
n = _n;
forn(i, 0, n - 2) {
g[A[i] + 1].eb(B[i] + 1, D[i]);
g[B[i] + 1].eb(A[i] + 1, D[i]);
}
dfs(1, 0);
forn(i, 1, C) {
forn(j, 1, timer - (1 << i) + 1) {
mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
}
}
forn(i, 2, timer) lg[i] = lg[i >> 1] + 1;
}
ll Query(int S, int X[], int T, int Y[]) {
if (S <= 10 && T <= 10) {
ll res = ool;
forn(i, 0, S - 1) {
forn(j, 0, T - 1) {
int v = X[i] + 1, u = Y[j] + 1;
int lca = get(tin[u], tin[v]);
res = min(res, lvl[u] + lvl[v] - 2 * lvl[lca]);
}
}
return res;
}
forn(i, 0, S - 1)
tp[X[i] + 1] = 1;
forn(i, 0, T - 1)
tp[Y[i] + 1] = 2;
ll res = dfs2(1, 0);
forn(i, 0, S - 1)
tp[X[i] + 1] = 0;
forn(i, 0, T - 1)
tp[Y[i] + 1] = 0;
return res;
}
