#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<ll> vll;
typedef pair<long long, long long> pll;
typedef pair<char, ll> ci;
typedef pair<string, ll> si;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<string> vs;
#define pb push_back
#define fi first
#define se second
#define whole(v) v.begin(), v.end()
#define rwhole(v) v.rbegin(), v.rend()
const ll inf = 10000000000000000;
#define fro front
vector<vector<ii>> x(500005);
void Init(int N, int A[], int B[], int D[]) {
for(ll i = 0; i < N; ++i){
x[A[i]].pb(ii(B[i], D[i]));
x[B[i]].pb(ii(A[i], D[i]));
}
}
long long Query(int S, int X[], int T, int Y[]) {
ll ans = inf;
priority_queue<ii, vector<ii>, greater<ii>> q;
ll dist[500005];
for(int i = 0; i < 500005; ++i){
dist[i] = inf;
}
for(ll i = 0; i < S; ++i){
q.push(ii(0, X[i]));
dist[X[i]] = 0;
}
while(!q.empty()){
ll price = q.top().fi;
ll node = q.top().se;
q.pop();
if(price != dist[node]){
continue;
}
for(auto e:x[node]){
if(dist[e.fi] > dist[node] + e.se){
q.push(ii(price + e.se, e.fi));
dist[e.fi] = price + e.se;
}
}
}
for(int i = 0; i < T; ++i){
ans = min(ans, dist[Y[i]]);
}
return ans;
}
