#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){
// cout <<u<<" "<<dp[u]<<'\n';;
// cout <<dp[v.fi]<<" "<<v.fi<<'\n';
if(g[u]==1){
ans=min(ans,dp[u]);
}
for(ii v:a1[u]){
if(v.fi==cha)continue;
// cout<<v.fi<<" "<<dp[v.fi]<<" "<<u<<" "<<v.se<<" "<<dp[u]<<" "<<l[u]<<'\n';
if(l[u]==v.fi){
if(dp[v.fi]>=dp2[u]+v.se){
l[v.fi]=u;
dp2[v.fi]=dp[v.fi];
dp[v.fi]=dp2[u]+v.se;
}
}
else{
if(dp[v.fi]>=dp[u]+v.se){
l[v.fi]=u;
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;dp2[u]=0;
}
for(ii v:a1[u]){
if(v.fi==cha)continue;
dfs2(v.fi,u);
if(dp[u]>=dp[v.fi]+v.se){
// cout <<u<<" "<<v.fi<<'\n';
l[u]=v.fi;
dp2[u]=dp[u];
dp[u]=dp[v.fi]+v.se;
}
}
}
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;
}
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];
}
void Init(int n,int A[],int B[],int D[]){
for(int i=0;i<n-1;++i){
int u=A[i];
int v=B[i];
++u,++v;
a[u].emb(v,D[i]);
a[v].emb(u,D[i]);
}
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];
}
for(int i=1;i<=n;++i)dp[i]=dp2[i]=1e18,g[i]=-1,l[i]=0;
}
long long Query(int S,int x[],int T,int y[]){
ans=1e18;
for(int i=0;i<S;++i){
x[i]++;
res.emb(x[i]);
g[x[i]]=1;
}
for(int i=0;i<T;++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]));
}
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()){
// if(i==4&&s.top()==1)cout<<kc(i,s.top())<<'\n';
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);
// for(int i=1;i<=10;++i)cout <<l[i]<<" ";
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();
l[i]=0;
}
res.clear();
return ans;
}
// int q,n,A[N],B[N],D[N],x[N],y[N],T,S;
// main(){
// ios_base::sync_with_stdio(false);
// cin.tie(NULL);
// cout.tie(NULL);
// freopen("a.inp","r",stdin);
// freopen("a.out","w",stdout);
// cin >> n >> q;
// for(int i=0;i<n-1;++i){
// cin >> A[i] >> B[i] >> D[i];
// }
// Init(n,A,B,D);
// while(q--){
// cin >> S >> T;
// for(int i=0;i<S;++i){
// cin >> x[i];
// }
// for(int i=0;i<T;++i)cin >> y[i];
// cout << Query(S,x,T,y)<<'\n';
// // for(int i=1;i<=n;++i)cout <<g[i]<<'\n';
// // cout <<res.size()<<'\n';
// }
// }
