#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<vector<pair<int,int>>> adj(N);
for (int i = 0; i<M; i++){
int a = R[i][0];
int b = R[i][1];
int w = L[i];
adj[a].push_back({b,w});
adj[b].push_back({a,w});
}
vector<long long> bst(N,1e18), scd(N, 1e18);
priority_queue<pair<long long,long long>> pq; //-dist, node
for (int i = 0; i<K; i++){
int x = P[i];
pq.push({0LL,(long long)x});
bst[x] = 0LL;
scd[x] = 0LL;
}
while (!pq.empty()){
auto u = pq.top(); pq.pop();
auto [dist, node] = u;
dist = -dist;
if (dist > scd[node]) continue;
for (auto e : adj[node]){
auto [a, w] = e;
int vl = w + dist;
if (vl < bst[a]){
scd[a] = bst[a];
bst[a] = vl;
pq.push({-scd[a],a});
}
else if (vl >= bst[a] && vl < scd[a]){
scd[a] = vl;
pq.push({-scd[a],a});
}
}
}
int dddd = scd[0];
return dddd;
}
