#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); }
template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); }
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define all(x) x.begin(), x.end()
#define TASK "nonsense"
/// end of template ///
const int N = 5e5 + 55;
const ll inf = 1e17;
int n,dep[N],up[N][20],tg=0,st[N],en[N];
ll dis[N];
vector<ii> adj[N];
void dfs(int u, int pa)
{
st[u]=++tg;
up[u][0]=pa;
for (int j=1; j<20; ++j) if ((1<<j)<dep[u]) up[u][j]=up[up[u][j-1]][j-1];
for (ii p : adj[u])
{
int v=p.fi,w=p.se;
if (v==pa) continue;
dep[v]=dep[u]+1;
dis[v]=dis[u]+w;
dfs(v,u);
}
en[u]=++tg;
}
int findLca(int u, int v)
{
if (dep[u]<dep[v]) swap(u,v);
int k=dep[u]-dep[v];
for (int j=0; j<20; ++j) if ((k>>j)&1) u=up[u][j];
if (u==v) return u;
for (int j=19; j>=0; --j) if ((1<<j)<dep[u])
{
if (up[u][j]!=up[v][j])
{
u=up[u][j];
v=up[v][j];
}
}
return up[u][0];
}
bool inside(int pa, int u)
{
return (st[pa]<=st[u] && st[u]<=en[pa]);
}
void Init(int _n, int A[], int B[], int D[]) {
n=_n;
for (int i=0; i<n-1; ++i)
{
int u=A[i],v=B[i],w=D[i];
adj[u].pb({v,w});
adj[v].pb({u,w});
}
dep[0]=1;
dis[0]=0;
dfs(0,-1);
}
bool dfsTimer(int u, int v)
{
return st[u]<st[v];
}
int a[N*2],k,nroot,id[N];
vector<pair<int,ll>> nadj[N];
stack<int> stk;
pair<pair<ll,int>,pair<ll,int>> dp[N];
void update(int u, int v, ll w)
{
pair<ll,int> cm;
if (dp[v].fi.se==u) cm=dp[v].se;
else cm=dp[v].fi;
cm.fi+=w;
if (id[v]==1) minimize(cm,make_pair(w,v));
if (cm<dp[u].fi) dp[u].se=dp[u].fi,dp[u].fi=cm;
else if (cm<dp[u].se) dp[u].se=cm;
}
void notreroot(int u, int pa)
{
dp[u]=make_pair(make_pair(inf,-1),make_pair(inf,-1));
for (pair<int,ll> p : nadj[u])
{
int v=p.fi; ll w=p.se;
if (v==pa) continue;
notreroot(v,u);
update(u,v,w);
}
// cerr<<u<<' '<<dp[u].fi.fi<<' '<<dp[u].fi.se<<' '<<dp[u].se.fi<<' '<<dp[u].se.se<<'\n';
}
ll reroot(int u, int pa)
{
ll ans=inf;
// cerr<<"DSDASDIASHDIU "<<u<<' '<<id[u]<<'\n';
if (id[u]==-1) minimize(ans,dp[u].fi.fi);
for (pair<int,ll> p : nadj[u])
{
int v=p.fi; ll w=p.se;
if (v==pa) continue;
pair<pair<ll,int>,pair<ll,int>> old=dp[v];
dp[v]=make_pair(make_pair(inf,-1),make_pair(inf,-1));
for (pair<int,ll> gaugau : nadj[v])
{
update(v,gaugau.fi,gaugau.se);
}
minimize(ans,reroot(v,u));
dp[v]=old;
}
return ans;
}
long long Query(int S, int X[], int T, int Y[]) {
k=0;
for (int j=0; j<S; ++j) a[++k]=X[j],id[X[j]]=-1;
for (int j=0; j<T; ++j) a[++k]=Y[j],id[Y[j]]=1;
for (int i=2; i<=k; ++i) a[i+k-1]=findLca(a[i],a[i-1]);
k=2*k-1;
sort(a+1,a+1+k,dfsTimer);
k=unique(a+1,a+1+k)-a-1;
// cerr<<k<<'\n';
// for (int i=1; i<=k; ++i) cerr<<a[i]<<' ';
// cerr<<'\n';
nroot=a[1];
// cerr<<nroot<<'\n';
while (!stk.empty()) stk.pop();
stk.push(nroot);
for (int i=2; i<=k; ++i)
{
int u=a[i];
while (!inside(stk.top(),u)) stk.pop();
int v=stk.top();
ll w=dis[u]-dis[v];
// cerr<<u<<' '<<v<<' '<<w<<'\n';
nadj[u].pb({v,w});
nadj[v].pb({u,w});
stk.push(u);
}
// for (int i=0; i<n; ++i) cerr<<id[i]<<' ';
// cerr<<'\n';
notreroot(nroot,-1);
ll ans=reroot(nroot,-1);
// reset
for (int j=0; j<S; ++j) id[X[j]]=0;
for (int j=0; j<T; ++j) id[Y[j]]=0;
for (int i=1; i<=k; ++i) vector<pair<int,ll>>().swap(nadj[a[i]]);
return ans;
}
