#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,par[MAXN][20],depth[MAXN];
ll dist[MAXN];
vector<pair<int,int>> adj[MAXN];
void dfsInit(int u){
for(pair<int,int>& v : adj[u])
if(v.fi!=par[u][0]){
dist[v.fi]=dist[u]+v.se, par[v.fi][0]=u, depth[v.fi]=depth[u]+1;
for(int i = 1; i<20; ++i)
par[v.fi][i]=par[par[v.fi][i-1]][i-1];
dfsInit(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]);
dfsInit(1);
}
inline void lift(int &x, int k){
for(int i = 0; i<20; ++i)
if((k>>i)&1) x=par[x][i];
}
inline int LCA(int x, int y){
if(depth[x]!=depth[y]){
if(depth[x]<depth[y]) swap(x,y);
lift(x,depth[x]-depth[y]);
}
if(x==y) return x;
for(int i = 19; i>=0; --i)
if(par[x][i]!=par[y][i]) x=par[x][i], y=par[y][i];
return par[x][0];
}
ll rs;
bool A[MAXN],B[MAXN];
pair<ll,ll> dfs(int u){
ll minA=1e18, minB=1e18;
for(pair<int,int>& v : adj[u])
if(v.fi!=par[u][0]){
pair<ll,ll> p = dfs(v.fi);
minA=min(minA,p.fi), minB=min(minB,p.se);
}
if(A[u]) minA=min(minA,dist[u]);
if(B[u]) minB=min(minB,dist[u]);
rs=min(rs,minA+minB-2*dist[u]);
return {minA,minB};
}
ll Query(int n, int a[], int m, int b[]){
rs=1e18;
for(int i = 0; i<n; ++i)
++a[i];
for(int i = 0; i<m; ++i)
++b[i];
if(1ll*n*m*__lg(n)<=n){
for(int i = 0; i<n; ++i)
for(int j = 0; j<m; ++j)
rs=min(rs,dist[a[i]]+dist[b[j]]-2*dist[LCA(a[i],b[j])]);
return rs;
}
for(int i = 0; i<n; ++i)
A[a[i]]=1;
for(int i = 0; i<m; ++i)
B[b[i]]=1;
dfs(1);
for(int i = 0; i<n; ++i)
A[a[i]]=0;
for(int i = 0; i<m; ++i)
B[b[i]]=0;
return rs;
}
