#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k, l) for(int i = (j); i < (k); i += (l))
#define FORD(i, j, k, l) for(int i = (j); i >= (k); i -= (l))
#define REP(i, n) FOR(i, 0, n, 1)
#define REPD(i, n) FORD(i, n, 0, 1)
#define pb push_back
const int INF = (int)1e9;
typedef long long ll;
const ll INFF = (ll)1e18;
int n;
vector<vector<array<ll, 2>>> vg;
vector<vector<array<ll, 2>>> g;
vector<ll> depth;
vector<int> lev;
vector<vector<int>> nxt;
vector<int> in;
vector<int> out;
vector<bool> type_a;
vector<bool> type_b;
vector<array<ll, 2>> dp;
int t = 0;
void dfs(int v, int p, ll d){
in[v] = t++;
depth[v] = d;
if(p != -1){
lev[v] = lev[p] + 1;
}
nxt[0][v] = p;
FOR(i, 1, 20, 1){
if(nxt[i - 1][v] != -1){
nxt[i][v] = nxt[i - 1][nxt[i - 1][v]];
}
}
for(auto x : g[v]){
if(x[0] == p) continue;
dfs(x[0], v, d + x[1]);
}
out[v] = t;
}
int lca(int u, int v){
if(lev[u] < lev[v])
swap(u, v);
FORD(i, 19, 0, 1){
if(lev[u] - (1 << i) >= lev[v]){
u = nxt[i][u];
}
}
if(u == v)
return u;
REPD(i, 19){
if(nxt[i][u] != nxt[i][v]){
u = nxt[i][u];
v = nxt[i][v];
}
}
return nxt[0][u];
}
int build_virtual_tree(vector<int> &vertices){
auto upper = [&](int u, int v){
return in[u] <= in[v] && out[u] >= out[v];
};
auto cmp = [&](int u, int v){
return in[u] < in[v];
};
sort(vertices.begin(), vertices.end(), cmp);
int up = vertices.size();
REP(i, up - 1){
vertices.pb(lca(vertices[i], vertices[i + 1]));
}
sort(vertices.begin(), vertices.end(), cmp);
vertices.erase(unique(vertices.begin(), vertices.end()), vertices.end());
for(int v : vertices){
vg[v].clear();
type_a[v] = false;
type_b[v] = false;
}
vector<int> stk;
stk.pb(vertices[0]);
FOR(i, 1, vertices.size(), 1){
while(stk.size() >= 2 && !upper(stk.back(), vertices[i])){
int u = stk.back();
stk.pop_back();
int v = stk.back();
ll w = abs(depth[u] - depth[v]);
vg[u].pb({v, w});
vg[v].pb({u, w});
}
stk.pb(vertices[i]);
}
while(stk.size() >= 2){
int u = stk.back();
stk.pop_back();
int v = stk.back();
ll w = abs(depth[u] - depth[v]);
vg[u].pb({v, w});
vg[v].pb({u, w});
}
return stk[0];
}
void solve(int v, int p, ll &ans){
dp[v] = {INFF, INFF};
for(auto x : vg[v]){
if(x[0] == p) continue;
solve(x[0], v, ans);
auto ar = dp[x[0]];
ar[0] += x[1];
ar[1] += x[1];
dp[v][0] = min(dp[v][0], ar[0]);
dp[v][1] = min(dp[v][1], ar[1]);
}
if(type_a[v])
dp[v][0] = 0;
if(type_b[v])
dp[v][1] = 0;
ans = min(ans, dp[v][0] + dp[v][1]);
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
vg.resize(n);
g.resize(n);
depth.resize(n);
nxt = vector<vector<int>>(20, vector<int>(n, -1));
in.resize(n);
out.resize(n);
lev.resize(n, 0);
type_a.resize(n, false);
type_b.resize(n, false);
dp.resize(n);
REP(i, n - 1){
g[A[i]].pb({B[i], D[i]});
g[B[i]].pb({A[i], D[i]});
}
dfs(0, -1, 0);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> vertices;
REP(i, S){
vertices.pb(X[i]);
}
REP(i, T){
vertices.pb(Y[i]);
}
int root = build_virtual_tree(vertices);
REP(i, S){
type_a[X[i]] = true;
}
REP(i, T){
type_b[Y[i]] = true;
}
ll ans = INFF;
solve(root, -1, ans);
return ans;
}
