#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
//#define int long long
template <class _T>
bool chmin(_T &x, const _T &y){
bool flag = false;
if ( x > y ){
x = y; flag |= true;
}
return flag;
}
template <class _T>
bool chmax(_T &x, const _T &y){
bool flag = false;
if ( x < y ){
x = y; flag |= true;
}
return flag;
}
const long long inf = 1e15 + 1;
vector <pair<int,int>> g[500005];
int n;
void Init(int N, int A[], int B[], int D[]) {
for ( int i = 0; i + 1 < N; i++ ){
g[A[i]].pb({B[i], D[i]});
g[B[i]].pb({A[i], D[i]});
} n = N;
}
long long Query(int S, int X[], int T, int Y[]) {
priority_queue <pair<long long,int>> q;
vector <long long> dis(n, inf);
for ( int i = 0; i < S; i++ ){
dis[X[i]] = 0;
q.push({0, X[i]});
}
while ( !q.empty() ){
auto [val, u] = q.top();
q.pop(); val *= -1;
if ( dis[u] != val ){
continue;
}
for ( auto [v, w]: g[u] ){
if ( chmin(dis[v], dis[u] + w) ){
q.push({-dis[v], v});
}
}
}
long long ans = inf;
for ( int i = 0; i < T; i++ ){
chmin(ans, dis[Y[i]]);
}
return ans;
}
