#include<bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=5e5+5;
int n,m,p[N][21],level[N],sz[N],l[N],r[N],type[N],node[N*2];
long long mn[N][2],dep[N],res;
vector<pii>adj[N];
vector<int>g[N];
int cnt=0;
void dfs(int u)
{
for(int i=1;i<=20;i++) p[u][i]=p[p[u][i-1]][i-1];
cnt++;
l[u]=cnt;
for(auto&to:adj[u])
{
int v=to.fi;
int w=to.se;
if(v==p[u][0]) continue;
p[v][0]=u;
dep[v]=dep[u]+w;
level[v]=level[u]+1;
dfs(v);
}
r[u]=cnt;
}
int lca(int x,int y)
{
if(level[x]>level[y]) swap(x,y);
int diff=level[y]-level[x];
for(int k=20;k>=0;k--) if(diff>>k&1) y=p[y][k];
if (x==y) return x;
for(int k=20;k>=0;k--)
{
if (p[x][k]!=p[y][k])
{
x=p[x][k];
y=p[y][k];
}
}
return p[x][0];
}
bool isParent(int p,int u)
{
return (l[p]<=l[u]&&l[u]<=r[p]);
}
bool lf(const int &x,const int &y)
{
return l[x]<l[y];
}
void Init(int N,int A[],int B[],int D[])
{
n=N;
cnt=0;
for(int i=1;i<=n;i++) type[i]=-1;
for(int i=0;i<n-1;i++)
{
int u=A[i];
int v=B[i];
int w=D[i];
u++,v++;
adj[u].push_back(mp(v,w));
adj[v].push_back(mp(u,w));
}
dfs(1);
}
void go(int u,int par=-1)
{
if(type[u]==0) mn[u][0]=dep[u];
if(type[u]==1) mn[u][1]=dep[u];
for(auto&v:g[u])
{
if(v==par) continue;
go(v,u);
res=min(res,mn[u][0]+mn[v][1]-2*dep[u]);
res=min(res,mn[v][0]+mn[u][1]-2*dep[u]);
mn[u][0]=min(mn[u][0],mn[v][0]);
mn[u][1]=min(mn[u][1],mn[v][1]);
}
}
long long Query(int S,int X[],int T,int Y[])
{
int total_num=0;
for(int i=0;i<S;i++)
{
X[i]++;
type[X[i]]=0;
total_num++;
node[total_num]=X[i];
}
for(int i=0;i<T;i++)
{
Y[i]++;
type[Y[i]]=1;
total_num++;
node[total_num]=Y[i];
}
sort(node+1,node+total_num+1,lf);
total_num=unique(node+1,node+total_num+1)-node-1;
int now=total_num;
for(int i=1;i<now;i++)
{
total_num++;
node[total_num]=lca(node[i],node[i+1]);
}
sort(node+1,node+total_num+1,lf);
total_num=unique(node+1,node+total_num+1)-node-1;
for(int i=1;i<=total_num;i++)
{
g[node[i]].clear();
mn[node[i]][0]=1e18;
mn[node[i]][1]=1e18;
}
stack<int>st;
st.push(node[1]);
for(int i=2;i<=total_num;i++)
{
while(!st.empty()&&!isParent(st.top(),node[i])) st.pop();
if(!st.empty())
{
int par=st.top();
g[par].push_back(node[i]);
g[node[i]].push_back(par);
}
st.push(node[i]);
}
res=1e18;
go(node[1]);
for(int i=0;i<S;i++) type[X[i]]=-1;
for(int i=0;i<T;i++) type[Y[i]]=-1;
return res;
}
