#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Vertex{
int i, d;
Vertex(){}
Vertex(int _i, int _d): i(_i), d(_d) {}
bool operator<(const Vertex &V) const{
return d > V.d;
}
};
vector<pair<int, int>> adj[100100];
vector<int> val[100100];
bool visited[100100];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for (int i=0;i<M;i++){
adj[R[i][0]].emplace_back(R[i][1], L[i]);
adj[R[i][1]].emplace_back(R[i][0], L[i]);
}
priority_queue<Vertex> pq;
for (int i=0;i<K;i++){
pq.emplace(P[i], 0);
}
while(!pq.empty()){
auto s = pq.top(); pq.pop();
//printf(" %d %d\n", s.i, s.d);
if (!s.i) return s.d;
if (visited[s.i]) continue;
for (auto &v:adj[s.i]) if (!visited[v.first]){
val[v.first].push_back(v.second + s.d);
sort(val[v.first].begin(), val[v.first].end());
if (val[v.first].size()>2) val[v.first].pop_back();
if (val[v.first].size()==2) pq.emplace(v.first, val[v.first][1]);
}
}
exit(1);
}
