#include "factories.h"
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define ll long long
using namespace std;
const ll N=5005;
const ll INF=1e18;
vector<pair<ll,ll>> g[N];
ll b[N],s[N];
void Init(int n, int A[], int B[], int D[]) {
for(ll i=0; i<n; i++){
g[A[i]].pb({B[i],D[i]});
g[B[i]].pb({A[i],D[i]});
}
return;
}
long long Query(int S, int X[], int T, int Y[]) {
for(ll i=0; i<N; i++) b[i]=0,s[i]=INF;
for(ll i=0; i<T; i++) b[Y[i]]=1;
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
for(ll i=0; i<S; i++) pq.push({0,X[i]}), s[X[i]]=0;
while(true){
auto p=pq.top();
pq.pop();
if(b[p.se]==1) return p.fi;
for(auto v : g[p.se]){
if(s[v.fi]<=p.fi+v.se) continue;
pq.push({p.fi+v.se,v.fi});
s[v.fi]=p.fi+v.se;
}
}
}
