#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(200006);
vector<ll>dead(200006);
vector<ll>parC(200006,-1);
vector<vector<pair<ll,ll>>>adj(200006);
vector<vector<ll>>up(200006,vector<ll>(20,-1));
vector<ll>best(200006,1e15);
vector<ll>def(200006,0);
void dfs(ll x,ll p,ll d){
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];
}
for(auto [y,w] : adj[x]){
if(y!=p) dfs(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 = 0; i < n-1; i++){
adj[A[i]].pb({B[i],D[i]});
adj[B[i]].pb({A[i],D[i]});
}
dfs(1,-1,0);
build(1,-1);
}
ll Query(int S, int A[], int T, int B[]){
ll s = S;
ll t = T;
for(ll i = 0; i < t; i++){
ll id = A[i];
while(id != -1){
best[id] = min(best[id],dist(id,A[i]));
id = parC[id];
}
}
ll ans = 1e18;
for(ll i = 0; i < t; i++){
ll c = B[i];
while(c != -1){
ans = min(ans,best[c]+dist(c,B[i]));
c = parC[c];
}
}
return ans;
}
