#include <bits/stdc++.h>
#include "crocodile.h"
#define ll long long
#define ii pair<ll, ll>
#define ff first
#define ss second
#define pb(x) push_back(x)
#define fto(i, a, b, x) for (int i = a; i <= b; i += x)
using namespace std;
const ll maxN = 1e6+5;
const ll INF = 1e16;
int n, m, k, p[maxN];
vector<ii> dothi[maxN];
ii mn[maxN];
void solve() {
priority_queue<ii, vector<ii>, greater<ii>> pq;
fto(i, 1, n, 1) mn[i] = {INF, INF};
fto(i, 1, k, 1) {
mn[p[i]] = {0, 0};
pq.push({0, p[i]});
}
while (pq.size()) {
ll d = pq.top().ff;
int u = pq.top().ss;
pq.pop();
if (d > mn[u].ss) continue;
for (ii x : dothi[u]) {
int v = x.ff; ll w = x.ss;
ll val = d + w;
if (val < mn[v].ff) {
mn[v].ss = mn[v].ff;
mn[v].ff = val;
if (mn[v].ss != INF) pq.push({mn[v].ss, v});
} else if (val < mn[v].ss) {
mn[v].ss = val;
pq.push({mn[v].ss, v});
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
n = N; m = M; k = K;
fto(i, 1, n, 1) dothi[i].clear();
fto(i, 1, m, 1) {
int u = R[i-1][0] + 1, v = R[i-1][1] + 1, w = L[i-1];
dothi[u].emplace_back(v, w);
dothi[v].emplace_back(u, w);
}
fto(i, 1, k, 1) p[i] = P[i-1] + 1;
solve();
return (int)mn[1].ss;
}
