#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pair<int, int>> vpi;
namespace kactl {
template <class T>
struct RMQ {
vector<vector<T>> jmp;
void init(const vector<T> &V)
{
jmp.resize(1, vector<T>(V));
for(int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
jmp.emplace_back(sz(V) - pw * 2 + 1);
rep(j, 0, sz(jmp[k]))
jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
}
}
T query(int a, int b)
{
assert(a < b); // or return inf if a == b
int dep = 31 - __builtin_clz(b - a);
return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
}
};
struct LCA {
int T = 0;
vi time, path, ret;
vl depth;
RMQ<int> rmq;
void init(vector<vpi> &C)
{
time.resize(sz(C));
depth.resize(sz(C));
dfs(C, 0, -1);
rmq.init(ret);
}
void dfs(vector<vpi> &C, int v, int par)
{
time[v] = T++;
for(auto [y, d] : C[v]) {
if(y != par) {
path.push_back(v), ret.push_back(time[v]);
depth[y] = depth[v] + d;
dfs(C, y, v);
}
}
}
int lca(int a, int b)
{
if(a == b) return a;
tie(a, b) = minmax(time[a], time[b]);
return path[rmq.query(a, b)];
}
ll dist(int a, int b) { return depth[a] + depth[b] - 2 * depth[lca(a, b)]; }
};
vpi compressTree(LCA &lca, const vi &subset)
{
vi li = subset, &T = lca.time;
auto cmp = [&](int a, int b) { return T[a] < T[b]; };
sort(all(li), cmp);
int m = sz(li) - 1;
rep(i, 0, m)
{
int a = li[i], b = li[i + 1];
li.push_back(lca.lca(a, b));
}
sort(all(li), cmp);
li.erase(unique(all(li)), li.end());
vpi ret = {pii(li[0], li[0])};
rep(i, 0, sz(li) - 1)
{
int a = li[i], b = li[i + 1];
ret.emplace_back(lca.lca(a, b), b);
}
return ret;
}
}; // namespace kactl
using namespace kactl;
const int nax = 500123;
ll toX[nax], toY[nax];
vi ch[nax];
#define x first
#define y second
LCA lca;
void Init(int N, int A[], int B[], int D[])
{
vector<vpi> g(N);
for(int i = 0; i < N; i++) {
toX[i] = toY[i] = 1e18;
}
for(int i = 0; i < N - 1; i++) {
g[A[i]].emplace_back(B[i], D[i]);
g[B[i]].emplace_back(A[i], D[i]);
}
lca.init(g);
}
ll ans;
void chmin(ll &a, ll b)
{
if(a > b) {
a = b;
}
}
void dfs(int u)
{
for(auto to : ch[u]) {
dfs(to);
chmin(toX[u], toX[to] + lca.dist(u, to));
chmin(toY[u], toY[to] + lca.dist(u, to));
}
ans = min(ans, toX[u] + toY[u]);
}
ll Query(int S, int X[], int T, int Y[])
{
vi s;
for(int i = 0; i < S; i++) {
toX[X[i]] = 0;
s.emplace_back(X[i]);
}
for(int i = 0; i < T; i++) {
toY[Y[i]] = 0;
s.emplace_back(Y[i]);
}
vpi r = compressTree(lca, s);
for(int i = 1; i < sz(r); i++) {
ch[r[i].x].emplace_back(r[i].y);
}
ans = 1e18;
dfs(r[0].x);
for(auto [_, i] : r) {
toX[i] = toY[i] = 1e18;
ch[i].clear();
}
return ans;
}
