#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;
#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
bool mini(auto &x, const auto &y) {
if (y < x) {
x = y;
return 1;
}
return 0;
}
bool maxi(auto &x, const auto &y) {
if (y > x) {
x = y;
return 1;
}
return 0;
}
const int N = (int) 5e5 + 123;
const int L = 20;
int n;
vector<pair<int, int>> g[N];
ll len[N];
int depth[N];
int up[N][L];
int tin[N], tout[N];
void precalc(int v, int f = 0) {
static int tmr = 0;
tin[v] = tmr++;
up[v][0] = f;
rep(i, 1, L) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
for (auto &e : g[v]) {
int u = e.first;
if (u == f) {
continue;
}
len[u] = len[v] + e.second;
depth[u] = depth[v] + 1;
precalc(u, v);
}
tout[v] = tmr - 1;
}
bool test(int mask, int bit) {
return mask & (1 << bit);
}
int go(int v, int h) {
rep(i, 0, L) {
if (test(h, i)) {
v = up[v][i];
}
}
return v;
}
int lca(int u, int v) {
if (depth[u] < depth[v]) {
swap(u, v);
}
u = go(u, depth[u] - depth[v]);
if (u == v) {
return u;
}
per(i, L - 1, 0) {
int uu = up[u][i], vv = up[v][i];
if (uu != vv) {
u = uu, v = vv;
}
}
return up[u][0];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
rep(i, 0, n - 1) {
g[A[i]].pb({B[i], D[i]});
g[B[i]].pb({A[i], D[i]});
}
precalc(0);
}
vector<int> adj[N];
bool in(int v, int u) {
return tin[u] <= tin[v] && tout[v] <= tout[u];
}
ll dp1[N], dp2[N];
ll dfs(int v) {
ll res = LINF;
for (int u : adj[v]) {
mini(res, dfs(u));
mini(dp1[v], dp1[u] + len[u] - len[v]);
mini(dp2[v], dp2[u] + len[u] - len[v]);
}
mini(res, dp1[v] + dp2[v]);
return res;
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> p;
rep(i, 0, S) {
p.pb(X[i]);
}
rep(i, 0, T) {
p.pb(Y[i]);
}
sort(all(p), [] (int i, int j) {
return tin[i] < tin[j];
});
vector<int> q;
rep(i, 0, sz(p) - 1) {
q.pb(lca(p[i], p[i + 1]));
}
for (int v : q) {
p.pb(v);
}
sort(all(p));
p.resize(unique(all(p)) - p.begin());
sort(all(p), [] (int i, int j) {
return tin[i] < tin[j];
});
for (int v : p) {
dp1[v] = LINF;
dp2[v] = LINF;
adj[v].clear();
}
vector<int> st;
st.pb(p[0]);
rep(i, 1, sz(p)) {
int v = p[i];
while (!in(v, st.back())) {
st.pop_back();
}
adj[st.back()].pb(v);
st.pb(v);
}
rep(i, 0, S) {
dp1[X[i]] = 0;
}
rep(i, 0, T) {
dp2[Y[i]] = 0;
}
return dfs(p[0]);
}
