#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;
#define File freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V) V.begin(),V.end()
#define setprec(x) fixed << setprecision(x)
#define Mp(a,b) make_pair(a,b)
#define len(V) (int)(V.size())
#define sep ' '
#define endl '\n'
#define pb push_back
#define fi first
#define sec second
#define popcount(x) __builtin_popcount(x)
#define lid u<<1
#define rid (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 1e6 + 10,SQ=320,LOG=21;
const ll inf = 2e17 , MD = 1e9 + 7;
inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
vector<pii> g[N];
int st[N],ft[N],tim=1;
int par[N][LOG];
int dis[N];
vector<pair<int,long long>> adj[N];
int col[N];
ll dp[N],dp1[N],dp2[N];
ll ps[N];
void dfs(int u,int p){
st[u] = tim++;
par[u][0] = p;
dis[u] = (u == p ? 0 : dis[p] + 1);
for(int j =1 ;j < LOG;j++) par[u][j] = par[par[u][j-1]][j-1];
for(auto h : g[u]){
if(h.fi != p) {
ps[h.fi] = ps[u] + h.sec;
dfs(h.fi,u);
}
}
ft[u] = tim;
}
int lift(int u,int k){
for(int j = 0 ;j < LOG;j++){
if(k&(1<<j)) u = par[u][j];
}
return u;
}
int lca(int u,int v){
if(dis[u] > dis[v]) swap(u,v);
v =lift(v,dis[v] - dis[u]);
if(u==v) return u;
for(int j = LOG-1;j >= 0;j--){
if(par[u][j] != par[v][j]){
u = par[u][j],v= par[v][j];
}
}
return par[u][0];
}
void Init(int N,int A[],int B[],int D[]){
int n = N;
for(int i = 0 ; i < n - 1;i++){
g[A[i]].pb({B[i],D[i]});
g[B[i]].pb({A[i],D[i]});
}
fill(col,col+n+2,0);
dfs(0,0);
}
void DFS(int u){
dp[u] = dp1[u] = dp2[u] = inf;
for(auto h : adj[u]){
DFS(h.fi);
dp1[u] = min(dp1[u],dp1[h.fi] + h.sec);
dp2[u] = min(dp2[u],dp2[h.fi] + h.sec);
dp[u] = min(dp[u],dp[h.fi]);
}
ll m1 = inf;
for(auto h : adj[u]){
dp[u] = min(dp[u],dp1[h.fi] + h.sec + m1);
m1 = min(m1,dp2[h.fi] + h.sec);
}
m1 = inf;
for(auto h : adj[u]){
dp[u] = min(dp[u],dp2[h.fi] + h.sec + m1);
m1 = min(m1,dp1[h.fi] + h.sec);
}
if(col[u] == 1) dp1[u] = 0;
if(col[u] == 2) dp2[u] = 0;
if(col[u] == 1) dp[u] = min(dp[u],dp2[u]);
if(col[u] == 2) dp[u] = min(dp[u],dp1[u]);
}
long long Query(int S, int X[], int T, int Y[]){
vector<int> ver;
for(int j = 0 ; j < S;j++) ver.pb(X[j]);
for(int j = 0 ;j < S;j++) col[X[j]] = 1;
for(int j = 0 ; j < T;j++) ver.pb(Y[j]);
for(int j = 0 ; j < T;j++) col[Y[j]] = 2;
sort(all(ver),[&](int u,int v){
return (st[u] < st[v]);
});
int ln = len(ver);
for(int j = 0 ; j + 1 < ln;j++) ver.pb(lca(ver[j],ver[j+1]));
sort(all(ver),[&](int u,int v){
return st[u] < st[v];
});
ver.resize(unique(all(ver))-ver.begin());
function<bool(int,int)> is_anc = [&](int u,int v){
return (st[u] <= st[v] && ft[v] <= ft[u]);
};
vector<int> stk;
stk.pb(ver[0]);
for(int j = 1;j < len(ver);j++){
while(!stk.empty() && !is_anc(stk.back(),ver[j])){
stk.pop_back();
}
adj[stk.back()].pb({ver[j],ps[ver[j]] - ps[stk.back()]});
stk.pb(ver[j]);
}
DFS(ver[0]);
for(auto h : ver) adj[h].clear();
for(int j = 0 ; j < S;j++) col[X[j]] = 0;
for(int j = 0 ; j < T;j++) col[Y[j]] = 0;
return dp[ver[0]];
}
