#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], in_q[maxN];
vector<ii> dothi[maxN];
ii mn[maxN];
void bfs () {
queue<int> q;
fto (i, 1, n, 1) mn[i] = {INF, INF}, in_q[i] = 0;
fto (i, 1, k, 1) {
mn[p[i]] = {0, 0};
q.push(p[i]);
in_q[p[i]] = 1;
}
while (q.size()) {
int u = q.front();
q.pop();
in_q[u] = 0;
for (ii x : dothi[u]) {
int v = x.ff; ll w = x.ss;
ll val = mn[u].ss + w;
int check = 1;
if (val < mn[v].ff) {
mn[v].ss = mn[v].ff;
mn[v].ff = val;
if (mn[v].ss != INF) check = 0;
}
else if (val < mn[v].ss) {
mn[v].ss = val;
check = 0;
}
if (!check && !in_q[v]) {
q.push(v);
in_q[v] = 1;
}
}
}
}
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;
bfs();
return (int)mn[1].ss;
}
