#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 int N=5e5+5;
const ll INF=1e18;
vector<pair<int,int>> g[N];
int tin[N],tout[N];
ll dist[N];
int pa[N][20];
int tt;
void dfs(int v, int p){
tin[v]=tt;
tt++;
pa[v][0]=p;
for(int 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;
}
int isanc(int a, int b){
return (tin[a]<tin[b]&&tout[a]>tout[b]);
}
int flca(int a, int b){
if(isanc(a,b)) return a;
if(isanc(b,a)) return b;
for(int i=19; i>=0; i--){
int na=pa[a][i];
if(!isanc(na,b)) a=na;
}
return pa[a][0];
}
void Init(int n, int A[], int B[], int D[]) {
for(int 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[]){
ll r=INF;
for(int i=0; i<S; i++){
for(int j=0; j<T; j++){
int l=flca(X[i],Y[j]);
r=min(r,dist[X[i]]+dist[Y[j]]-2*dist[l]);
}
}
return r;
}
