#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 vii vector<ll>
#define ump unordered_map
#define sz(a) (int)a.size()
#define getbit(i, j) ((i >> j) & 1)
#define addbit(i, j) (i | (1 << j))
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define fto(i, a, b, x) for (int i = a; i <= b; i += x)
#define fdto(i, a, b, x) for (int i = a; i >= b; i -= x)
#define all(x) x.begin(), x.end()
using namespace std;
const ll maxN = 1e6+5;
const ll INF = 1e18;
int n, m, k, p[maxN], deg[maxN];
vector<ii> dothi[maxN];
ii mn[maxN];
void bfs () {
queue<int> q;
fto (i, 1, n, 1) mn[i] = {INF, INF};
fto (i, 1, k, 1) q.push(p[i]), mn[p[i]] = {0, 0};
while (q.size()) {
int u = q.front();
q.pop();
for (ii x : dothi[u]) {
int v = x.ff; ll w = x.ss;
int check = 1;
if (mn[v].ff >= mn[u].ss + w && mn[u].ss + w != mn[v].ss) {
mn[v].ss = mn[v].ff, mn[v].ff = mn[u].ss + w;
if (mn[v].ss != INF) check = 0;
}
else if (mn[v].ss > mn[u].ss + w) mn[v].ss = mn[u].ss + w, check = 0;
if (!check) q.push(v);
}
}
}
int travel_plan(int N, int M, int R[][2],int L[], int K, int P[]) {
n = N;
m = M;
fto (i, 1, m, 1) {
int u = R[i-1][0], v = R[i-1][1], w = L[i-1];
u++; v++;
dothi[u].emplace_back(v, w);
dothi[v].emplace_back(u, w);
}
k = K;
fto (i, 1, k, 1) p[i] = P[i-1]+1;
bfs();
fto (i, 1, n, 1) dothi[i].clear();
return mn[1].ss;
}
