#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 () {
priority_queue<ii, vector<ii>, greater<ii>> pq;
fto (i, 1, n, 1) mn[i] = {INF, INF};
fto (i, 1, k, 1) pq.push({0, p[i]}), mn[p[i]] = {0, 0};
while (pq.size()) {
int u = pq.top().ss; ll du = pq.top().ff;
pq.pop();
if (du > mn[u].ss) continue;
for (ii x : dothi[u]) {
int v = x.ff; ll w = mn[u].ss + x.ss;
int check = 1;
if (mn[v].ff > w) {
mn[v].ss = mn[v].ff, mn[v].ff = w;
if (mn[v].ss != INF) check = 0;
}
else if (mn[v].ss > w) mn[v].ss = w, check = 0;
if (!check) 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;
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;
}
