#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<long long, long long>>> ed(N);
for(long long i = 0; i < M; ++i){
ed[R[i][0]].push_back({R[i][1], L[i]});
ed[R[i][1]].push_back({R[i][0], L[i]});
}
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
vector<pair<long long, long long>> paths(N, make_pair(1e18, 1e18));
for(int i = 0; i < K; ++i){
paths[P[i]] = {0, 0};
pq.push({0, P[i]});
}
while(!pq.empty()){
long long no = pq.top().second;
long long dis = pq.top().first;
pq.pop();
if(paths[no].second < dis){
continue;
}
//cout << no << " " << dis << endl;
for(auto e:ed[no]){
if(dis + e.second < paths[e.first].first){
paths[e.first].second = paths[e.first].first;
paths[e.first].first = dis + e.second;
pq.push({paths[e.first].second, e.first});
}else if(dis + e.second < paths[e.first].second){
paths[e.first].second = dis + e.second;
pq.push({paths[e.first].second, e.first});
}
}
}
return paths[0].second;
}
