#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);
int sz;
void Init(int N, int A[], int B[], int D[]) {
sz = N;
for(int i = 0; i < N-1; i++){
g[A[i]].pb({B[i], D[i]});
g[B[i]].pb({A[i], D[i]});
}
}
vector<ll> dif(n, inf);
priority_queue<array<ll,2>> q;
long long Query(int S, int X[], int T, int Y[]) {
q = priority_queue<array<ll,2>> ();
set<int> rem;
set<int> st;
for(int i = 0; i < T; i++){
st.insert(Y[i]);
}
for(int i = 0; i < S; i++){
q.push({0, X[i]});
dif[X[i]] = 0;
rem.insert(X[i]);
}
while(q.size()){
auto [dis, ps] = q.top();
q.pop();
//cout << dis << ' ' << ps << '\n';
dis = abs(dis);
if(dif[ps] < dis)continue;
if(st.count(ps)){
//for(int i = 0; i < sz; i++){
//cout << dif[i] << ' ' << i << '\n';
//}
//cout << '\n';
for(auto i:rem)dif[i] = inf;
return dis;
}
//cout << ps << '\n';
for(auto &[to, d]:g[ps]){
//cout << to << ' ' << d << '\n';
if(chmin(dif[to], dif[ps] + d)){
rem.insert(to);
q.push({-dif[to], to});
}
}
}
return inf;
}
