#include<bits/stdc++.h>
#include "factories.h"
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e18;
int n, q, tin[N], tout[N], h[N], timer, up[N][25];
vector<ii> g[N];
ll sum[N];
vector<pair<int, ll>> g2[N];
int type[N];
ll res, dp[N][5];
void dfs2(int u){
dp[u][0] = dp[u][1] = oo;
if(type[u] != -1){
dp[u][type[u]] = 0;
}
for(pair<int,ll> tmp : g2[u]){
int v = tmp.fi;
ll c = tmp.se;
dfs2(v);
res = min(res,
min(dp[u][0] + c + dp[v][1], dp[u][1] + c + dp[v][0]));
for(int t = 2; t--;){
dp[u][t] = min(dp[u][t], dp[v][t] + c);
}
}
}
void dfs(int u, int cur_par = -1){
tin[u] = ++timer;
for(ii tmp : g[u]){
int v = tmp.fi, c = tmp.se;
if(v == cur_par) continue;
sum[v] = sum[u] + c;
h[v] = h[u] + 1;
up[v][0] = u;
dfs(v, u);
}
tout[u] = timer;
}
void build_lca(){
h[1] = 1;
sum[1] = 0;
dfs(1);
for(int j = 1; j <= 19; j++){
for(int i = 1; i <= n; i++){
up[i][j] = up[up[i][j - 1]][j - 1];
}
}
}
int lca(int u, int v){
if(h[u] < h[v]) swap(u, v);
for(int j = 19; j >= 0; j--){
if(h[up[u][j]] >= h[v])
u = up[u][j];
}
if(u == v) return u;
for(int j = 19; j >= 0; j--){
if(up[u][j] != up[v][j]){
u = up[u][j];
v = up[v][j];
}
}
return up[u][0];
}
bool anc(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tin[v];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i = 0; i < n - 1; i++){
A[i]++; B[i]++;
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
// for(int i = 1; i <= n; i++){
// cout << i << ' ';
// for(ii x : g[i]) cout << x.fi << ' ';
// cout << '\n';
// }
build_lca();
}
long long Query(int S, int X[], int T, int Y[]) {
vector<ii> ord;
for(int i = 0; i < S; i++) X[i]++;
for(int i = 0; i < T; i++) Y[i]++;
for(int i = 0; i < S; i++)
ord.emplace_back(tin[X[i]], X[i]);
for(int i = 0; i < T; i++)
ord.emplace_back(tin[Y[i]], Y[i]);
sort(ord.begin(), ord.end());
for(int i = 0, sz = ord.size(); i < sz - 1; i++){
int x = lca(ord[i].se, ord[i + 1].se);
// cout << ord[i].se << ' ' << ord[i + 1].se << ' ' << x << '\n';
ord.emplace_back(tin[x], x);
}
sort(ord.begin(), ord.end());
ord.erase(unique(ord.begin(), ord.end()), ord.end());
stack<int> st;
for(ii x : ord){
g2[x.se].clear();
type[x.se] = -1;
}
for(int i = 0; i < S; i++)
type[X[i]] = 0;
for(int i = 0; i < T; i++)
type[Y[i]] = 1;
for(ii pi : ord){
int c = pi.se;
while(!st.empty() && !anc(st.top(), c)){
st.pop();
}
if(!st.empty()){
int r = st.top();
g2[r].emplace_back(c, sum[c] - sum[r]);
// g2[c].emplace_back(r, sum[c] - sum[r]);
}
st.push(c);
}
// for(int i = 0; i < ord.size(); i++){
// cout << ord[i].se << ": ";
// for(pair<long long, int> x : g2[ord[i].se])
// cout << x.fi << ' ' << x.se << ", ";
// cout << '\n';
// }
int root = ord.front().se;
// cout << root << '\n';
res = oo;
dfs2(root);
return res;
}
