#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int mxN = 5e5 + 5, LG = 20;
const long long inf = 1e18;
int ord[mxN], spt[LG][2 * mxN], lg[2 * mxN], tout[mxN];
long long dep[mxN], dp[mxN][2];
bool vs[mxN];
vector<pair<int, int>> g[mxN];
vector<int> graph[mxN];
int timer = 0;
void pre_dfs(int u) {
spt[0][ord[u] = ++timer] = u;
for (auto [v, w] : g[u]) {
if (!ord[v]) {
dep[v] = dep[u] + w;
pre_dfs(v);
spt[0][++timer] = u;
}
}
tout[u] = timer;
}
int mint(int u, int v) {
return ord[u] < ord[v] ? u : v;
}
int lca(int u, int v) {
int l = ord[u], r = ord[v];
if (l > r) {
swap(l, r);
}
int k = lg[r - l + 1];
return mint(spt[k][l], spt[k][r - (1 << k) + 1]);
}
long long dis(int u, int v) {
return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
void Init(int N, int *A, int *B, int *D) {
for (int i = 0; i < N - 1; ++i) {
++A[i], ++B[i];
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
pre_dfs(1);
for (int i = 2; i <= timer; ++i) {
lg[i] = lg[i / 2] + 1;
}
for (int j = 1; j < LG; ++j) {
for (int i = 1; i + (1 << j) - 1 <= timer; ++i) {
spt[j][i] = mint(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
}
}
for (int i = 1; i <= N; ++i) {
for (int j = 0; j < 2; ++j) {
dp[i][j] = inf;
}
}
}
long long Query(int S, int *X, int T, int *Y) {
vector<int> ver;
auto add = [&](int u) {
if (!vs[u]) {
ver.push_back(u);
vs[u] = 1;
}
};
for (int i = 0; i < T; ++i) {
add(++Y[i]);
dp[Y[i]][0] = dep[Y[i]];
}
for (int i = 0; i < S; ++i) {
add(++X[i]);
dp[X[i]][1] = dep[X[i]];
}
sort(ver.begin(), ver.end(), [&](int i, int j) {
return ord[i] < ord[j];
});
int m = ver.size();
for (int i = 1; i < m; ++i) {
add(lca(ver[i], ver[i - 1]));
}
sort(ver.begin(), ver.end(), [&](int i, int j) {
return ord[i] < ord[j];
});
vector<int> st;
for (int u : ver) {
while (st.size() && tout[st.back()] < ord[u]) {
st.pop_back();
}
if (st.size()) {
int p = st.back();
graph[p].push_back(u);
}
st.push_back(u);
}
long long ans = inf;
for (int i = ver.size() - 1; ~i; --i) {
int u = ver[i];
for (int v : graph[u]) {
for (int j = 0; j < 2; ++j) {
dp[u][j] = min(dp[u][j], dp[v][j]);
}
}
ans = min(ans, dp[u][0] + dp[u][1] - 2 * dep[u]);
}
for (int u : ver) {
vs[u] = 0;
graph[u].clear();
for (int j = 0; j < 2; ++j) {
dp[u][j] = inf;
}
}
return ans;
}
