#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ertunt return
#define rall(x) x.rbegin(),x.rend()
using namespace std;
ll lg = 20;
ll n;
vector<ll>sz(500005);
vector<ll>dead(500005);
vector<ll>parC(500005,-1);
vector<vector<pair<ll,ll>>>adj(500005);
ll up[500005][20];
vector<ll>best(500005,1e15);
vector<ll>def(500005,0);
void dfs(ll r){
stack<tuple<ll,ll,ll>>st;
st.push({r,-1,0});
while(!st.empty()){
auto [x,p,d] = st.top(); st.pop();
def[x] = d;
up[x][0] = p;
for(ll i = 1; i < lg; i++){
if(up[x][i-1] != -1) up[x][i] = up[up[x][i-1]][i-1];
else up[x][i] = -1;
}
for(auto [y,w] : adj[x]){
if(y!=p) st.push({y,x,d+w});
}
}
}
ll get_lca(ll x,ll y){
if(def[x] < def[y]) swap(x,y);
for(ll i = lg-1; i >= 0; i--){
if(up[x][i] != -1 && def[up[x][i]] >= def[y]){
x = up[x][i];
}
}
if(x == y) return x;
for(ll i = lg-1; i >= 0; i--){
if(up[x][i] != -1 && up[x][i] != up[y][i]){
x = up[x][i];
y = up[y][i];
}
}
return up[x][0];
}
ll dist(ll x,ll y){
return def[x] + def[y] - 2*def[get_lca(x,y)];
}
ll dfs_size(ll x,ll p){
sz[x] = 1;
for(auto [y,w] : adj[x]){
if(y != p && !dead[y]){
sz[x] += dfs_size(y,x);
}
}
return sz[x];
}
ll dfs_centroid(ll x,ll p,ll compsize){
for(auto [y,w] : adj[x]){
if(y != p && !dead[y]){
if(sz[y] > compsize/2) return dfs_centroid(y,x,compsize);
}
}
return x;
}
void build(ll x,ll p){
ll compsize = dfs_size(x,-1);
ll c = dfs_centroid(x,-1,compsize);
parC[c] = p;
dead[c] = 1;
for(auto [y,w] : adj[c]){
if(!dead[y]) build(y,c);
}
}
void Init(int N, int A[], int B[], int D[]){
n = N;
for(ll i = 1; i <= n; i++){
for(ll j = 0; j < lg; j++) up[i][j] = -1;
}
for(ll i = 0; i < n-1; i++){
adj[A[i]].pb({B[i],D[i]});
adj[B[i]].pb({A[i],D[i]});
}
dfs(0);
build(0,-1);
}
ll Query(int S, int A[], int T, int B[]){
vector<ll>v;
for(ll i = 0; i < S; i++){
ll x = A[i];
while(x != -1){
best[x] = min(best[x], dist(x,A[i]));
v.pb(x);
x = parC[x];
}
}
ll ans = 1e18;
for(ll i = 0; i < T; i++){
ll x = B[i];
while(x != -1){
ans = min(ans,best[x] + dist(x,B[i]));
x = parC[x];
}
}
for(auto x : v) best[x] = 1e15;
return ans;
}
