#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
#define foru(i,a,b) for(int i=(a); i<=(b); ++i)
#define ford(i,a,b) for(int i=(a); i>=(b); --i)
#define rep(i,a) for(int i=0; i<(a); ++i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define bit(s,i) (((s)>>(i))&1)
#define ii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ll long long
#define _ << " " <<
template <class X, class Y> bool maxi(X &x, Y y){return x<y?x=y,true:false;}
template <class X, class Y> bool mini(X &x, Y y){return x>y?x=y,true:false;}
const int NX=5e5+5;
const int LG=18;
int n;
int sz[NX],pcen[NX]; bool del[NX];
int up[NX][LG+1],h[NX]; ll d[NX];
ll minD[NX];
vector<ii> adj[NX];
void get_sz(int u, int p=-1){
sz[u]=1;
for(auto [v,w]:adj[u]) if(v!=p && !del[v]){
get_sz(v,u);
sz[u]+=sz[v];
}
}
int get_cen(int u, int szA, int p=-1){
for(auto [v,w]:adj[u]) if(v!=p && !del[v]){
if(sz[v]>szA/2) return get_cen(v,szA,u);
}
return u;
}
void decomp(int u, int lst=-1){
get_sz(u);
int cen=get_cen(u,sz[u]);
pcen[cen]=lst;
del[cen]=1;
for(auto [v,w]:adj[cen]) if(!del[v]) decomp(v,cen);
}
void dfs(int u, int p=-1){
for(auto [v,w]:adj[u]) if(v!=p){
h[v]=h[u]+1;
up[v][0]=u;
foru(i,1,LG) up[v][i]=up[up[v][i-1]][i-1];
d[v]=d[u]+w;
dfs(v,u);
}
}
int lca(int u, int v){
if(h[u]<h[v]) swap(u,v);
int d=h[u]-h[v];
foru(i,0,LG) if(bit(d,i)) u=up[u][i];
if(u==v) return u;
ford(i,LG,0){
if(up[u][i]!=up[v][i]){
u=up[u][i];
v=up[v][i];
}
}
return up[u][0];
}
ll dist(int u, int v){
return d[u]+d[v]-2*d[lca(u,v)];
}
void Init(int N, int A[], int B[], int D[]) {
n=N;
rep(i,n-1){
adj[A[i]].eb(B[i],D[i]);
adj[B[i]].eb(A[i],D[i]);
}
decomp(0);
dfs(0);
memset(minD,0x3f,sizeof(minD));
}
ll Query(int S, int X[], int T, int Y[]) {
rep(i,S){
int t=X[i];
while(t!=-1){
mini(minD[t], dist(X[i],t));
t=pcen[t];
}
}
//
ll res=1e18;
rep(i,T){
int t=Y[i];
while(t!=-1){
mini(res, minD[t]+dist(Y[i],t));
// cerr<<minD[t] _ dist(Y[i],t)<<'\n';
t=pcen[t];
}
}
rep(i,S){
int t=X[i];
while(t!=-1){
minD[t]=1e18;
t=pcen[t];
}
}
return res;
// return 0;
}
