#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define Mp make_pair
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl;
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input19.txt" , "r" , stdin) ;
const int N = 5e5+23, L=19;
const ll INF=1e18+23;
vector<pii> g[N];
int dead[N];
int sz[N], H[N], par[N];
ll h[N][L];
ll dp[N];
int n;
void dfs(int v, int p=0){
sz[v]=1;
for (auto [u, w]: g[v]) if(u!=p && !dead[u]){
dfs(u, v);
sz[v]+=sz[u];
}
}
int cent(int v, int num, int p=0){
for(auto [u, w]: g[v]) if(u!=p && !dead[u] && 2*sz[u]>num) return cent(u, num, v);
return v;
}
void DFS(int v, int hh, int p=0){
for (auto [u, w]: g[v])if(u!=p && !dead[u]){
h[u][hh]=h[v][hh]+w;
DFS(u, hh, v);
}
}
void Dec(int v=1, int hh=0, int p=0){
dfs(v);
v=cent(v, sz[v]);
H[v]=hh;
par[v]=p;
DFS(v, hh);
dead[v]=1;
for (auto [u, w]: g[v]) if(!dead[u]) Dec(u, hh+1, v);
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
for (int i=0; i<n-1; i++){
A[i]++;
B[i]++;
g[A[i]].pb({B[i], D[i]});
g[B[i]].pb({A[i], D[i]});
}
Dec();
for (int i=1; i<=n; i++) dp[i]=INF;
}
long long Query(int S, int X[], int T, int Y[]) {
for (int i=0; i<S; i++) X[i]++;
for (int i=0; i<T; i++) Y[i]++;
for (int i=0; i<S; i++){
int v=X[i];
while(v){
dp[v]=min(dp[v], h[X[i]][H[v]]);
v=par[v];
}
}
ll ans=INF;
for (int i=0; i<T; i++){
int v=Y[i];
while(v){
ans=min(ans, dp[v]+h[Y[i]][H[v]]);
v=par[v];
}
}
for (int i=0; i<S; i++){
int v=X[i];
while(v){
dp[v]=INF;
v=par[v];
}
}
return ans;
}
