#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
typedef long long ll;
const ll n = 5e5+5, inf = 1e17;
vector<vector<array<int,2>>> g(n);
vector<vector<int> > lc(22, vector<int> (n, 0));
vector<ll> ds(n, 0), tin(n),tout(n);
int tim = 0;
void dfs(int ps, int pr){
lc[0][ps] = pr;
for (int i = 1; i < 22; i++)
{
lc[i][ps] = lc[i-1][lc[i-1][ps]];
}
tin[ps] = tim++;
for(auto [to, d]:g[ps]){
if(to == pr)continue;
ds[to] = ds[ps] + d;
dfs(to, ps);
}
tout[ps] = tim++;
}
int lca (int a, int b){
if(tin[a] < tin[b] && tout[b] < tout[a])return a;
if(tin[b] < tin[a] && tout[a] < tout[b])return b;
for(int i = 20; i >= 0; i--){
int na = lc[i][a];
if(tin[na] < tin[b] && tout[b] < tout[na])continue;
a = na;
}
return lc[0][a];
}
ll get(int a,int b){
if(a == b)return 0;
int l = lca(a, b);
return ds[a] + ds[b] - 2*ds[l];
}
vector<int> vs(n, 0);
vector<int> have;
vector<int> sub(n, 0);
vector<vector<int>> par(n);
vector<ll> res(n,inf);
int ns;
void clacS(int v, int pr){
sub[v] = 1;
have.pb(v);
for(auto [to, d]:g[v]){
if(vs[to] || to == pr)continue;
clacS(to, v);
sub[v] += sub[to];
}
}
int centr(int ps, int pr){
for(auto [to, d]:g[ps]){
if(vs[to] || to == pr)continue;
if(sub[to] > ns/2)return centr(to, ps);
}
return ps;
}
void decm(int ps){
have.clear();
clacS(ps, ps);
ns = sub[ps];
int cur = centr(ps, ps);
for(auto v:have){
par[v].pb(cur);
}
vs[cur] = 1;
for(auto [to,d]:g[cur]){
if(vs[to])continue;
decm(to);
}
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N-1; i++){
g[A[i]].pb({B[i], D[i]});
g[B[i]].pb({A[i], D[i]});
}
dfs(0,0);
decm(0);
}
long long Query(int S, int X[], int T, int Y[]) {
vector<int> tod;
for(int i = 0; i < S; i++){
//cout << X[i] << ":\n";
for(auto v:par[X[i]]){
//cout << v << ' ';
chmin(res[v], get(v, X[i]));
//cout << get(v, X[i]) << '\n';
tod.pb(v);
}
//cout << '\n';
}
ll ans = inf;
for(int i = 0; i < T; i++){
for(auto v:par[Y[i]]){
chmin(ans, res[v] + get(v, Y[i]));
}
}
for(auto x:tod)res[x] = inf;
return ans;
}
