#include "factories.h"
#include<bits/stdc++.h>
/*#ifndef LOCAL
#define cerr if(0)cerr
#endif
*/
#define st first
#define nd second
using namespace std;
using ll = long long;
const int MAXN = 5e5+1;
const ll INF = 1e16+1;
vector<pair<int, int>> g[MAXN];
ll h[MAXN];
vector<int> euler, positions[MAXN];
int l[MAXN], r[MAXN];
void dfs(int x, int p) {
euler.push_back(x);
l[x] = r[x] = euler.size()-1;
for(auto i: g[x]) {
if(i.st != p) {
h[i.st] = h[x] + i.nd;
dfs(i.st, x);
euler.push_back(x);
r[x] = euler.size()-1;
}
}
}
struct Segtree {
vector<pair<ll, int>> tree;
int base;
vector<int> history;
void init(int sz) {
base=1;
while(base<sz) base *= 2;
tree.resize(2*base+1, {INF, -1});
}
void ins(int pos, pair<ll, int> val) {
history.push_back(pos);
pos += base;
while(pos) {
tree[pos] = min(tree[pos], val);
pos /= 2;
}
}
void del(int pos) {
pos += base;
while(pos) {
tree[pos] = {INF, -1};
pos /= 2;
}
}
void clr() {
for(int i: history) del(i);
history.clear();
}
int query(int L, int R) {
L += base;
R += base;
pair<ll, int> res = min(tree[L], tree[R]);
while(L/2 != R/2) {
if(L%2==0) {
res = min(res, tree[L+1]);
}
if(R%2==1) {
res = min(res, tree[R-1]);
}
L /= 2;
R /= 2;
}
return res.nd;
}
};
Segtree Tree, Ts, Tt;
int LCA(int x, int y) {
return Tree.query(min(l[x], l[y]), max(r[x], r[y]));
}
void Init(int N, int A[], int B[], int D[]) {
for(int i=0; i<N-1; ++i) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
dfs(0, 0);
Tree.init(euler.size());
for(int i=0; i<(int)euler.size(); ++i) {
positions[euler[i]].push_back(i);
Tree.ins(i, {h[euler[i]], euler[i]});
}
Ts.init(euler.size());
Tt.init(euler.size());
}
long long Query(int S, int X[], int T, int Y[]) {
vector<pair<int, int>> vec;
for(int i=0; i<S; ++i) {
vec.push_back({l[X[i]], X[i]});
for(int j: positions[X[i]]) {
Ts.ins(j, {h[X[i]], X[i]});
}
}
for(int i=0; i<T; ++i) {
vec.push_back({l[Y[i]], Y[i]});
for(int j: positions[Y[i]]) {
Tt.ins(j, {h[Y[i]], Y[i]});
}
}
sort(vec.begin(), vec.end());
ll ans = INF;
vector<int> nodes;
for(int i=1; i<(int)vec.size(); ++i) {
int lca = LCA(vec[i-1].nd, vec[i].nd);
nodes.push_back(lca);
}
for(int lca: nodes) {
int it1 = Ts.query(l[lca], r[lca]), it2 = Tt.query(l[lca], r[lca]);
if(it1 == -1 || it2 == -1) continue;
ans = min(ans, h[it1] + h[it2] - 2*h[lca]);
}
Ts.clr();
Tt.clr();
return ans;
}
