#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#include "factories.h"
#define ar array
const int M = 5e5 + 5;
vector<ar<int, 2>> edges[M];
int tin[M], tout[M], t, par[M][20];
long long d[M];
void dfs(int u, int p = -1){
tin[u] = ++t;
for(int i=1;i<20;i++) par[u][i] = par[par[u][i-1]][i-1];
for(auto x : edges[u]){
if(x[0] == p) continue;
d[x[0]] = d[u] + x[1];
par[x[0]][0] = u;
dfs(x[0], u);
} tout[u] = t;
}
int is[M];
bool iis(int a, int b) { return (tin[a] <= tin[b] && tout[b] <= tout[a]); }
int lca(int a, int b){
if(iis(a, b)) return a;
if(iis(b, a)) return b;
//~ cout<<tin[1]<<" "<<tout[1]<<" "<<tin[6]<<" "<<tout[6]<<"\n";
for(int i=19;~i;i--){
if(!iis(par[a][i], b)) a = par[a][i];
} // cout<<a<<"\n";
return par[a][0];
}
vector<int> tmp;
vector<ar<long long, 2>> ee[M];
long long dp[M], up[M];
void go(int u, int p = -1){
if(is[tmp[u]] == 1) dp[u] = 0;
for(auto x : ee[u]){
if(x[0] == p) continue;
go(x[0], u);
dp[u] = min(dp[u], dp[x[0]] + x[1]);
} // cout<<u<<" "<<dp[u]<<"\n";
}
void re(int u, int p = -1){
if(p == -1) up[u] = 1e18;
dp[u] = min(dp[u], up[u]);
if(is[tmp[u]] == 1) up[u] = 0;
for(auto x : ee[u]){
if(x[0] == p) continue;
up[x[0]] = up[u];
up[u] = min(up[u], dp[x[0]] + x[1]);
}
reverse(ee[u].begin(), ee[u].end());
up[u] = 1e18;
for(auto x : ee[u]){
if(x[0] == p) continue;
up[x[0]] = min(up[x[0]], up[u]);
up[u] = min(up[u], dp[x[0]] + x[1]);
up[x[0]] += x[1];
re(x[0], u);
}
}
void Init(int n, int a[], int b[], int d[]) {
for(int i=0;i+1<n;i++){
edges[a[i]].push_back({b[i], d[i]});
edges[b[i]].push_back({a[i], d[i]});
}
dfs(0);
}
long long Query(int s, int x[], int t, int y[]) {
if(s < t) swap(s, t), swap(x, y);
for(int i=0;i<s;i++){
is[x[i]] = 1;
}
long long res = 1e18;
for(int i=0;i<t;i++){
if(is[y[i]] == 1) res = 0;
is[y[i]] = 2;
}
if(!res){
for(int i=0;i<s;i++) is[x[i]] = 0;
for(int i=0;i<t;i++) is[y[i]] = 0;
return res;
}
tmp.clear();
for(int i=0;i<s;i++) tmp.push_back(x[i]);
for(int i=0;i<t;i++) tmp.push_back(y[i]);
sort(tmp.begin(), tmp.end(), [&](int i, int j) { return (tin[i] < tin[j]); });
int m = (int)tmp.size();
for(int i=1;i<m;i++){
tmp.push_back(lca(tmp[i-1], tmp[i]));
//~ cout<<tmp[i-1]<<" "<<tmp[i]<<" "<<lca(tmp[i-1], tmp[i])<<"\n";
}
sort(tmp.begin(), tmp.end(), [&](int i, int j) {
if(tin[i] != tin[j]) return (tin[i] < tin[j]);
return tout[i] > tout[j];
});
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
//~ for(auto x : tmp) cout<<x<<" ";
//~ cout<<"\n";
m = (int)tmp.size();
vector<int> nxt(m);
for(int i=0;i<m;i++){
int l = i + 1, r = m;
while(l < r){
int m = (l + r) >> 1;
if(tin[tmp[m]] <= tout[tmp[i]]) l = m + 1;
else r = m;
}
nxt[i] = l;
ee[i].clear();
dp[i] = 1e18;
}
//~ for(int i=0;i<m;i++) cout<<nxt[i]<<" ";
//~ cout<<"\n";
for(int i=0;i<m;i++){
int j = i + 1;
while(j < nxt[i]){
ee[i].push_back({j, d[tmp[j]] - d[tmp[i]]});
j = nxt[j];
}
}
go(0);
re(0);
for(int i=0;i<m;i++){
if(is[tmp[i]] == 2) res = min(res, dp[i]);
}
for(int i=0;i<m;i++) is[tmp[i]] = 0;
return res;
}
