#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
typedef long long ll;
/*
void openFiles() {
#ifdef KEK
assert(freopen("input.txt", "r", stdin));
assert(freopen("output.txt", "w", stdout));
#endif
}
*/
void IOoptimize() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
const int MAXN = 5e3 + 10;
const ll INF = 1e17;
vector<pair<int, ll>> g[MAXN];
int n;
int type[MAXN];
ll dist[MAXN];
void Init(int N, int A[], int B[], int D[]) {
IOoptimize();
n = N;
for (int i = 0; i < n - 1; i++) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
}
long long Query(int S, int X[], int T, int Y[]) {
memset(type, 0, sizeof(type));
for (int i = 0; i < T; i++) {
type[Y[i]] = 1;
}
for (int i = 0; i < n; i++) {
dist[i] = INF;
}
set<pair<ll, int>> q;
for (int i = 0; i < S; i++) {
dist[X[i]] = 0;
q.insert({dist[X[i]], X[i]});
}
while (!q.empty()) {
int cur = q.begin()->second;
q.erase(q.begin());
if (type[cur] == 1) {
return dist[cur];
}
for (auto v : g[cur]) {
if (dist[v.first] > dist[cur] + v.second) {
q.erase({dist[v.first], v.first});
dist[v.first] = dist[cur] + v.second;
q.insert({dist[v.first], v.first});
}
}
}
return INF;
}
