#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define tY template<typename T
tY> using vec = vector<T>;
tY> using maxheap = priority_queue<T>;
tY> using minheap = priority_queue<T,vec<T>,greater<T>>;
using ll = long long;
using vll = vec<ll>;
using vvll = vec<vll>;
using pll = pair<ll,ll>;
using str = string;
#define pb push_back
#define fi first
#define se second
#define sp << " "
#define sps << " " <<
#define nl << endl
#define all(a) a.begin(),a.end()
ll min(vll &a) { return *min_element(all(a)); }
ll max(vll &a) { return *max_element(all(a)); }
ll sum(vll &a) { return accumulate(all(a),0ll); }
void sort(vll &a) { sort(all(a)); }
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
ll n = N, m = M;
vec<vec<pll>> adj(n);
vec<bool> ending(n,0);
for(int i = 0; i < m; i++) {
ll u = R[i][0], v = R[i][1];
adj[u].pb({v,L[i]});
adj[v].pb({u,L[i]});
}
vll dists(n,1e15), dists2(n,1e15);
minheap<pll> pq;
for(int i = 0; i < K; i++) {
ll u = P[i];
ending[P[i]] = 1;
pq.push({0,u});
dists[u] = dists2[u] = 0;
}
while(!pq.empty()) {
auto [d,u] = pq.top();
pq.pop();
if(d != dists2[u]) continue;
for(auto[v,w] : adj[u]) {
if(d+w < dists[v]) {
if(dists[v] < dists2[v]) pq.push({dists[v],v});
dists2[v] = dists[v];
dists[v] = d+w;
} else if(d+w < dists2[v]) {
dists2[v] = d+w;
pq.push({d+w,v});
}
}
}
return dists2[0];
}
