#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 7;
const int LOG = 20;
vector<pair<int, int>> tree[MAXN];
int up[MAXN][LOG], depth[MAXN], tin[MAXN], tout[MAXN];
long long dist[MAXN];
int tim;
void dfs(int u, int p) {
tin[u] = ++tim;
up[u][0] = p;
for (int i = 1; i < LOG; i++) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
for (auto [v, w] : tree[u]) {
if (v == p) {
continue;
}
depth[v] = depth[u] + 1;
dist[v] = dist[u] + w;
dfs(v, u);
}
tout[u] = ++tim;
}
bool ck(int u, int v) {
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v) {
if (ck(u, v)) {
return u;
}
if (ck(v, u)) {
return v;
}
for (int i = LOG - 1; i >= 0; i--) {
if (!ck(up[u][i], v)) {
u = up[u][i];
}
}
return up[u][0];
}
long long get_dist(int u, int v) {
int anc = lca(u, v);
return dist[u] + dist[v] - 2 * dist[anc];
}
void Init(int N, int A[], int B[], int D[]) {
for (int i = 0; i < N - 1; i++) {
tree[A[i]].emplace_back(B[i], D[i]);
tree[B[i]].emplace_back(A[i], D[i]);
}
dfs(0, 0);
}
vector<int> vtree[MAXN];
bool isX[MAXN], isY[MAXN];
long long res;
void dfs_virtual(int u) {
long long bestX = isX[u] ? 0 : 1e18;
long long bestY = isY[u] ? 0 : 1e18;
for (int v : vtree[u]) {
dfs_virtual(v);
long long d = get_dist(u, v);
bestX = min(bestX, (long long) (isX[v] ? d : 1e18));
bestY = min(bestY, (long long) (isY[v] ? d : 1e18));
res = min(res, (long long) bestX + bestY);
}
isX[u] = (bestX == 0);
isY[u] = (bestY == 0);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> nodes;
for (int i = 0; i < S; i++) {
nodes.push_back(X[i]);
isX[X[i]] = true;
}
for (int i = 0; i < T; i++) {
nodes.push_back(Y[i]);
isY[Y[i]] = true;
}
sort(nodes.begin(), nodes.end(), [](int a, int b) {
return tin[a] < tin[b];
});
int sz = nodes.size();
for (int i = 0; i+1 < sz; ++i) {
nodes.push_back(lca(nodes[i], nodes[i+1]));
}
sort(nodes.begin(), nodes.end(), [](int a, int b) {
return tin[a] < tin[b];
});
nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
vector<int> stk;
for (int u : nodes) {
vtree[u].clear();
}
for (int u : nodes) {
while (!stk.empty() && !ck(stk.back(), u)) stk.pop_back();
if (!stk.empty()) {
vtree[stk.back()].push_back(u);
}
stk.push_back(u);
}
res = 1e18;
dfs_virtual(nodes[0]);
for (int u : nodes) {
isX[u] = isY[u] = false;
}
return res;
}
