#include "factories.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<ll, ll>
using namespace std;
const ll M = 5e5+3, R=1e16, L=25;
int n;
vector<pii> graf[M], vg[M];
int tin[M], tout[M], tt=0, par[M][L];
ll dist[M];
int tp[M];
void dfs(int v, int p)
{
par[v][0] = p;
for(int i=1; i<L; i++)
par[v][i] = par[par[v][i-1]][i-1];
tin[v] = ++tt;
for(auto [u,d] : graf[v])
if(p != u)
dist[u] = dist[v]+d,
dfs(u,v);
tout[v] = ++tt;
}
bool isanc(int v, int u)
{
return (tin[v] <= tin[u] && tout[u] <= tout[v]);
}
int lca(int v, int u)
{
if(isanc(v,u)) return v;
if(isanc(u,v)) return u;
for(int i=L-1; i>=0; i--)
if(!isanc(par[v][i], u))
v = par[v][i];
return par[v][0];
}
void add_edge(int u, int v)
{
if(u == v) return;
ll d = abs(dist[u] - dist[v]);
vg[u].push_back({v, d});
vg[v].push_back({u, d});
}
int create_vg(vector<int> v)
{
sort(v.begin(), v.end(), [](int a, int b){
return tin[a] < tin[b];
});
for(int i=int(v.size())-2; i>=0; i--)
v.push_back(lca(v[i], v[i+1]));
sort(v.begin(), v.end(), [](int a, int b){
return tin[a] < tin[b];
});
for(auto x: v) vg[x].clear();
v.push_back(v[0]);
vector<int> ve;
ve.push_back(v[0]);
for(int i=1; i<v.size(); i++)
{
while(!isanc(ve.back(), v[i]))
{
add_edge(ve.back(), ve[ve.size()-2]);
ve.pop_back();
}
ve.push_back(v[i]);
}
while(ve.size() > 1)
{
add_edge(ve.back(), ve[ve.size()-2]);
ve.pop_back();
}
return ve[0];
}
ll ans;
pii dfs2(int v, int p)
{
pii r = {R, R};
if(tp[v] == 1) r.fi = 0;
if(tp[v] == 2) r.se = 0;
for(auto x: vg[v])
if(x.fi != p)
{
pii r2 = dfs2(x.fi, v);
r.fi = min(r.fi, r2.fi+x.se);
r.se = min(r.se, r2.se+x.se);
}
ans = min(ans, r.fi+r.se);
return r;
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i=0; i<N; i++)
graf[A[i]].push_back({B[i], D[i]}),
graf[B[i]].push_back({A[i], D[i]});
dfs(0,0);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> v;
memset(tp,0,sizeof tp);
ans = R;
for(int i=0; i<S; i++) v.push_back(X[i]), tp[X[i]] = 1;
for(int i=0; i<T; i++) v.push_back(Y[i]), tp[Y[i]] = 2;
int k = create_vg(v);
dfs2(k, k);
return ans;
}
