#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int mxN = 5e5 + 10;
const long long inf = 5e18;
vector<pair<int, int>> adj[mxN];
int st[mxN], en[mxN], tin = 0;
long long sum[mxN], seg[mxN * 2];
void dfs(int u = 0, int par = 0){
st[u] = ++tin;
for(auto [v, w] : adj[u]){
if(v ^ par){
sum[v] = (long long) sum[u] + w;
dfs(v, u);
}
}
en[u] = tin;
}
void update(int idx, long long val){
idx += tin;
seg[idx] = val;
while(idx > 1){
idx >>= 1;
seg[idx] = min(seg[idx << 1], seg[idx << 1 | 1]);
}
}
long long query(int l, int r){
l += tin, r += tin;
long long ans = inf;
while(l <= r){
if(l & 1) ans = min(ans, seg[l ++]);
if(r & 1 ^ 1) ans = min(ans, seg[r --]);
l >>= 1, r >>= 1;
}
return ans;
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N - 1; ++i){
adj[A[i]].push_back({B[i], D[i]});
adj[B[i]].push_back({A[i], D[i]});
}
dfs();
for(int i = 0; i < 2 * mxN; ++i) seg[i] = inf;
}
long long get(vector<int> A, vector<int> B){
long long ans = inf;
for(auto it : A) update(st[it], sum[it]);
for(auto it : B) ans = min(ans, query(st[it], en[it]) - sum[it]);
for(auto it : A) update(st[it], inf);
return ans;
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> a, b;
for(int i = 0; i < S; ++i) a.push_back(X[i]);
for(int i = 0; i < T; ++i) b.push_back(Y[i]);
return min(get(a, b), get(b, a));
}
