#include <bits/stdc++.h>
#include "crocodile.h"
#define ll long long
#define fi first
#define se second
#define pii pair<ll, ll>
#define all(a) a.begin(), a.end()
using namespace std;
#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif
const ll mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e18;
ll n, m, k, p[mn];
vector <pii> a[mn];
pii d[mn];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
n = 1ll * N, m = 1ll * M, k = 1ll * K;
for(ll i = 0; i < m; i++) {
ll u = 1ll * R[i][0] + 1ll, v = 1ll * R[i][1] + 1ll, w = 1ll * L[i];
a[u].push_back({v, w});
a[v].push_back({u, w});
}
priority_queue <pii, vector <pii>, greater<pii>> pq;
for(ll i = 1; i <= n; i++) d[i] = {inf, inf};
for(ll i = 0; i < k; i++) {
p[i] = 1ll * P[i] + 1ll;
d[p[i]] = {0, 0};
pq.push({0, p[i]});
}
while(pq.size()) {
auto [c, u] = pq.top();
pq.pop();
if(c > d[u].se) continue;
for(auto [v, w] : a[u]) {
ll nw = c + w;
if(d[v].fi > nw) {
d[v].se = d[v].fi;
d[v].fi = nw;
}
else if(d[v].se > nw) d[v].se = nw;
if(d[v].se < inf) pq.push({d[v].se, v});
}
}
for(int i = 0; i < n; i++) a[i].clear();
return d[1].se;
}
// Don't wanna lose anymore T_T
// Never let me go - Kazuo Ishiguro
