#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 500010, LG = 19;
const ll inf = 1ll << 55;
ll dep[MAX_N];
int anc[LG][MAX_N], in[MAX_N], out[MAX_N], n;
vector<pair<int,int>> edge[MAX_N];
void dfs1(int x, int lst) {
static int t;
in[x] = ++t;
for (auto [u, w] : edge[x]) if (u != lst) {
anc[0][u] = x;
dep[u] = dep[x] + w;
dfs1(u, x);
}
out[x] = t;
}
bool isanc(int a, int b) { return in[a] <= in[b] && out[a] >= out[b]; }
int getlca(int a, int b) {
for (int d = LG-1;d >= 0;--d)
if (!isanc(anc[d][a], b))
a = anc[d][a];
return isanc(a, b) ? a : anc[0][a];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0;i < N-1;++i) {
int a = A[i], b = B[i], c = D[i];
edge[a].pb(b, c);
edge[b].pb(a, c);
}
dfs1(0, 0);
for (int d = 1;d < LG;++d)
for (int i = 0;i < N;++i)
anc[d][i] = anc[d-1][ anc[d-1][i] ];
}
struct conf {
int vis[MAX_N], time;
void reset() { ++time; }
void insert(int i) { vis[i] = time; }
int count(int i) { return vis[i] == time; }
}svis, tvis;
long long Query(int S, int X[], int T, int Y[]) {
ll res = inf;
svis.reset(), tvis.reset();
for (int i = 0;i < S;++i)
svis.insert(X[i]);
for (int i = 0;i < T;++i)
tvis.insert(Y[i]);
vector<int> loc(X, X+S); loc.insert(end(loc), Y, Y+T);
sort(AI(loc), [&](int a, int b) {
return in[a] < in[b]; });
loc.resize(unique(AI(loc)) - begin(loc));
{
int os = loc.size();
for (int i = 0;i + 1 < os;++i)
loc.pb(getlca(loc[i], loc[i+1]));
}
sort(AI(loc), [&](int a, int b) {
return in[a] < in[b]; });
loc.resize(unique(AI(loc)) - begin(loc));
vector<int> stk;
vector<pair<ll,ll>> dp;
auto update = [&](int a, int b) {
auto &[a0, a1] = dp[a];
auto &[b0, b1] = dp[b];
chmin(res, a0 + b1 - 2 * dep[stk[a]]);
chmin(res, a1 + b0 - 2 * dep[stk[a]]);
chmin(a0, b0), chmin(a1, b1);
};
// DE(S), debug(X, X+S);
// DE(T), debug(Y, Y+T);
for (int x : loc) {
while (stk.size() > 1) {
if (isanc(stk.back(), x)) break;
update(stk.size() - 2, stk.size() - 1);
stk.pop_back(), dp.pop_back();
}
stk.pb(x);
dp.pb(inf, inf);
if (svis.count(x)) dp.back().first = dep[x];
if (tvis.count(x)) dp.back().second = dep[x];
//DE(x, dp.back().first, dp.back().second, svis.count(x), tvis.count(x));
}
while (stk.size() > 1) {
update(stk.size() - 2, stk.size() - 1);
stk.pop_back(), dp.pop_back();
}
return res;
}
