#include "factories.h"
#include<bits/stdc++.h>
#define ii pair<int,long long>
#define se second
#define fi first
#define emb emplace_back
using namespace std;
const int N=5e5+5,lg=19;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
return u+rd()%(v-u+1);
}
vector<ii>a[N],a1[N];
int tin[N],t,tout[N],g[N],h[N],up[N][lg+5],l[N];
long long f[N],ans,dp[N],dp2[N];
void dfs3(int u,int cha){
if(g[u]==1){
ans=min(ans,dp[u]);
// cout << u <<" ";
}
for(ii v:a1[u]){
if(v.fi==cha)continue;
if(l[u]==v.fi){
if(dp[v.fi]>=dp2[u]+v.se){
l[u]=v.fi;
dp2[v.fi]=dp[v.fi];
dp[v.fi]=dp2[u]+v.se;
}
}
else{
if(dp[v.fi]>=dp[u]+v.se){
l[u]=v.fi;
dp2[v.fi]=dp[v.fi];
dp[v.fi]=dp[u]+v.se;
}
}
dfs3(v.fi,u);
}
}
void dfs2(int u,int cha){
if(g[u]==0){
dp[u]=0;
}
for(ii v:a1[u]){
if(v.fi==cha)continue;
dfs2(v.fi,u);
if(dp[u]>=dp[v.fi]+v.se){
l[u]=v.fi;
dp2[u]=dp[u];
dp[u]=dp[v.fi]+v.se;
}
// else if(dp[u]==dp[v.fi]+v.se)dp2[u]
// dp[u]=min(dp[v.fi]+v.se,dp[u]);
}
}
void dfs(int u,int cha){
tin[u]=++t;
for(ii v:a[u]){
if(v.fi==cha)continue;
h[v.fi]=h[u]+1;
up[v.fi][0]=u;
f[v.fi]=f[u]+v.se;
dfs(v.fi,u);
}
tout[u]=t;
}
stack<int>s;
int lca(int u,int v){
if(h[u]<h[v])swap(u,v);
for(int j=lg;j>=0;--j)if(h[u]-h[v]>=(1<<j))u=up[u][j];
if(u==v)return u;
for(int j=lg;j>=0;--j){
if(up[u][j]!=up[v][j]){
u=up[u][j];
v=up[v][j];
}
}
return up[u][0];
}
long long kc(int u,int v){
return f[u]+f[v]-f[lca(u,v)]*2;
}
int x[N],y[N],ss,tt;
vector<int>res,res1;
bool cmp(int x,int y){
return tin[x]<tin[y];
}
bool cha(int x,int y){
return tout[x]>=tout[y]&&tin[x]<=tin[y];
}
// int g[N];
// void solve(){
// cin >> n >> q;
// for(int i=1;i<n;++i){
// int u,v,w;
// cin >> u >> v >> w;
// ++u,++v;
// a[u].emb(v,w);
// a[v].emb(u,w);
// }
// for(int i=1;i<=n;++i)dp[i]=dp2[i]=1e18,g[i]=-1;
// dfs(1,-1);
// for(int j=1;j<=lg;++j)
// for(int i=1;i<=n;++i){
// up[i][j]=up[up[i][j-1]][j-1];
// }
// // memset(g,-1,sizeof g);
// }
void Init(int q,int w[],int e[],int r[]){
for(int i=0;i<q-1;++i){
int u=w[i];
int v=e[i];
++u,++v;
a[u].emb(v,r[i]);
a[v].emb(u,r[i]);
}
dfs(1,-1);
for(int j=1;j<=lg;++j)
for(int i=1;i<=q;++i){
up[i][j]=up[up[i][j-1]][j-1];
}
for(int i=1;i<=q;++i)dp[i]=1e18;
memset(g,-1,sizeof g);
}
long long Query(int S,int u[],int T,int v[]){
// while(q--){
ans=1e18;
// cin >> ss >> tt;
for(int i=0;i<ss;++i){
// cin >> x[i];
x[i]++;
res.emb(x[i]);
g[x[i]]=1;
// cout <<x[i]<<" ";
}
for(int i=0;i<tt;++i){
// cin >> y[i];
y[i]++;
res.emb(y[i]);
g[y[i]]=0;
}
sort(res.begin(),res.end(),cmp);
int sz=res.size();
for(int i=0;i<sz-1;++i){
res.emb(lca(res[i],res[i+1]));
// cout <<res[i]<<" "<<res[i+1]<<" "<<lca(res[i],res[i+1])<<'\n';
}
sort(res.begin(),res.end());
res.erase(unique(res.begin(),res.end()),res.end());
sort(res.begin(),res.end(),cmp);
for(int i:res){
while(!s.empty()&&!cha(s.top(),i))s.pop();
if(!s.empty()){
a1[s.top()].emb(i,kc(i,s.top()));
a1[i].emb(s.top(),kc(i,s.top()));
}
s.push(i);
}
dfs2(res[0],-1);
dfs3(res[0],-1);
while(!s.empty())s.pop();
for(int i:res){
g[i]=-1;dp[i]=dp2[i]=1e18;
if(a1[i].size())
a1[i].clear();
// cout <<i<<" ";
}
res.clear();
return ans;
// }
}
// main()
// {
// srand(time(0));
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
// if(fopen(task".inp","r")){
// freopen(task".inp","r",stdin);
// freopen(task".out","w",stdout);
// }
// int t=1;
// // cin >> t;
// while(t--){
// solve();
// cout<<'\n';
// }
// }
