#include "factories.h"
#include<bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using ll = long long;
const int N = 2e5 + 12;
int n, sz[N], head[N], p[N];
ll dep[N];
vector<array<int, 2>> g[N];
struct MNode { ll a = 1ll<<55;
MNode() {}
MNode(ll x) : a(x) {}
friend MNode operator+(const MNode &a, const MNode &b) {
return MNode(min(a.a, b.a));
}
};
template<class Node>
struct SegTree {
int n;
vector<Node> tree;
SegTree(int N) : n(N), tree(2*n) {}
void upd(int pos, Node val) {
for(tree[pos+=n]=val;pos/=2;)
tree[pos] = tree[2*pos]+tree[2*pos+1];
}
Node query(int l, int r) {
Node res;
for(l += n, r += n; l < r; l>>=1,r>>=1) {
if(l&1) res = res + tree[l++];
if(r&1) res = tree[--r] + res;
}
return res;
}
};
int tin[N], tout[N], timer = 0;
void sizes(int v) {
sz[v] = 1;
for(auto &F : g[v]) {
auto i = F[0];
auto w = F[1];
p[i] = v;
dep[i] = dep[v]+w;
g[i].erase(find(all(g[i]), array<int, 2>{v, w}));
sizes(i);
sz[v] += sz[i];
if(sz[i] > sz[g[v][0][0]])
swap(g[v][0], F);
}
}
void hld(int v) {
tin[v] = timer++;
for(auto &[i, w] : g[v]) {
head[i] = i == g[v][0][0] ? head[v] : i;
hld(i);
}
tout[v] = timer;
}
SegTree<MNode> st(0);
void Init(int N, int A[], int B[], int D[]) {
n = N;
st = SegTree<MNode>(n);
for(int i = 0; i+1 < n; i++) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
sizes(0);
hld(0);
}
template<int undo>
void update(int v) {
st.upd(tin[v], undo ? MNode() : MNode(dep[v]));
//cout << tin[v] << " _ " << dep[v] << " " << st.query(0, n).a << endl;
}
void query(int v, ll &ans) {
ll md = dep[v];
while(true) {
ans = min(ans, st.query(tin[v], tout[v]).a+md-2*dep[v]);
if(!v) break;
v = p[head[v]];
}
}
void solve(int s, int x[], int t, int y[], ll &ans) {
for(int i = 0; i < s; i++)
update<0>(x[i]);
//cout << "F " << tin[0] << " " << tout[0] << endl;
for(int i = 0; i < t; i++)
query(y[i], ans);
for(int i = 0; i < s; i++)
update<1>(x[i]);
}
long long Query(int s, int x[], int t, int y[]) {
ll ans = 1ll<<60;
solve(s, x, t, y, ans);
solve(t, y, s, x, ans);
return ans;
}
