#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<pair<int, int>> adj[N];
for(int i = 0;i<M;i++){
adj[R[i][0]].push_back({R[i][1], L[i]});
adj[R[i][1]].push_back({R[i][0], L[i]});
}
vector<int> mn(N, INF), smn(N, INF);
priority_queue<pair<int, int>> pq;
for(int i = 0;i<K;i++){
mn[P[i]] = smn[P[i]] = 0;
pq.push({0, P[i]});
}
while(!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if(d > smn[u]) continue;
for(auto [v, w] : adj[u]){
bool f = 0;
if(d + w < mn[v]){
f = 1;
smn[v] = mn[v];
mn[v] = d + w;
}else if(d + w < smn[v]){
f = 1;
smn[v] = d + w;
}
if(f){
pq.push({smn[v], v});
}
}
}
return smn[0];
}
