#include "factories.h"
#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 5e5+5;
const string NAME = "";
int n,sz[MAXN];
ll dist[MAXN];
bool del[MAXN];
vector<pair<int,int>> adj[MAXN];
vector<pair<int,ll>> centroid[MAXN];
void GetSize(int u, int par){
sz[u]=1;
for(pair<int,int>& v : adj[u])
if(!del[v.fi]&&v.fi!=par) GetSize(v.fi,u), sz[u]+=sz[v.fi];
}
int Centroid(int u, int par, const int& N){
for(pair<int,int>& v : adj[u])
if(!del[v.fi]&&v.fi!=par&&sz[v.fi]>N>>1) return Centroid(v.fi,u,N);
return u;
}
void dfs(const int& root, int u, int par, ll dist){
centroid[u].pb(root,dist);
for(pair<int,int>& v : adj[u])
if(!del[v.fi]&&v.fi!=par) dfs(root,v.fi,u,dist+v.se);
}
void CentroidDecomposition(int u){
GetSize(u,0);
int root=Centroid(u,0,sz[u]);
centroid[root].pb(root,0);
for(pair<int,int>& v : adj[root])
if(!del[v.fi]) dfs(root,v.fi,root,v.se);
del[root]=1;
for(pair<int,int>& v : adj[root])
if(!del[v.fi]) CentroidDecomposition(v.fi);
}
void Init(int N, int a[], int b[], int d[]){
n=N;
for(int i = 0; i<n; ++i)
++a[i], ++b[i], adj[a[i]].pb(b[i],d[i]), adj[b[i]].pb(a[i],d[i]);
memset(dist,0x3f,sizeof(dist));
CentroidDecomposition(1);
}
ll Query(int n, int a[], int m, int b[]){
ll rs=1e18;
for(int i = 0; i<n; ++i){
++a[i];
for(pair<int,ll>& p : centroid[a[i]])
dist[p.fi]=min(dist[p.fi],p.se);
}
for(int i = 0; i<m; ++i){
++b[i];
for(pair<int,ll>& p : centroid[b[i]])
rs=min(rs,dist[p.fi]+p.se);
}
for(int i = 0; i<n; ++i){
for(pair<int,ll>& p : centroid[a[i]])
dist[p.fi]=1e18;
}
return rs;
}
