#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std;
const ll N=5e5+5;
const ll INF=1e18;
vector<pair<ll,ll>> g[N];
vector<pair<ll,ll>> vtg[N];
ll tin[N],tout[N],c[N];
ll dist[N],min1[N],min2[N];
ll pa[N][20];
ll tt,best;
void dfs(ll v, ll p){
tin[v]=tt;
tt++;
pa[v][0]=p;
for(ll i=1; i<20; i++) pa[v][i]=pa[pa[v][i-1]][i-1];
for(auto u : g[v]){
if(u.fi==p) continue;
dist[u.fi]=dist[v]+u.se;
dfs(u.fi,v);
}
tout[v]=tt;
tt++;
return;
}
ll isanc(ll a, ll b){
return (tin[a]<=tin[b]&&tout[a]>=tout[b]);
}
ll flca(ll a, ll b){
if(isanc(a,b)) return a;
if(isanc(b,a)) return b;
for(ll i=19; i>=0; i--){
ll na=pa[a][i];
if(!isanc(na,b)) a=na;
}
return pa[a][0];
}
void connect(ll a, ll b){
if(a==b) return;
ll d=abs(dist[a]-dist[b]);
vtg[a].pb({b,d});
vtg[b].pb({a,d});
return;
}
ll create(vector<ll> nodes){
sort(nodes.begin(),nodes.end(),[](ll &a, ll &b){
return tin[a]<tin[b];
});
for(ll i=nodes.size()-2; i>=0; i--) nodes.pb(flca(nodes[i],nodes[i+1]));
sort(nodes.begin(),nodes.end(),[](ll &a, ll &b){
return tin[a]<tin[b];
});
vector<ll> ve;
ve.pb(nodes[0]);
for(ll i=1; i<nodes.size(); i++){
while(!isanc(ve.back(),nodes[i])){
connect(ve.back(),ve[ve.size()-2]);
ve.pop_back();
}
ve.pb(nodes[i]);
}
while(ve.size()>1){
connect(ve.back(),ve[ve.size()-2]);
ve.pop_back();
}
return ve[0];
}
void dfs2(ll v, ll p){
min1[v]=min2[v]=INF;
for(auto u : vtg[v]){
if(u.fi==p) continue;
dfs2(u.fi,v);
min1[v]=min(min1[v],min1[u.fi]+u.se);
min2[v]=min(min2[v],min2[u.fi]+u.se);
}
if(c[v]==1) min1[v]=0;
if(c[v]==2) min2[v]=0;
best=min(best,min1[v]+min2[v]);
vtg[v].clear();
return;
}
void Init(int n, int A[], int B[], int D[]) {
for(ll i=0; i<n; i++){
g[A[i]].pb({B[i],D[i]});
g[B[i]].pb({A[i],D[i]});
}
dfs(0,0);
return;
}
long long Query(int S, int X[], int T, int Y[]){
vector<ll> nodes;
for(int i=0; i<S; i++) nodes.pb(X[i]), c[X[i]]=1;
for(int i=0; i<T; i++) nodes.pb(Y[i]), c[Y[i]]=2;
ll root=create(nodes);
best=INF;
dfs2(root,root);
for(ll i=0; i<S; i++) c[X[i]]=0;
for(ll i=0; i<T; i++) c[X[i]]=0;
return best;
}
