#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> Pair;
const int Nmax = 1e5 + 5;
vector<Pair> v[Nmax];
priority_queue< Pair, vector<Pair>, greater<Pair> > heap;
int dist[Nmax];
bool used[Nmax];
vector<int> best[Nmax];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
int i;
for(i=0; i<M; ++i)
{
int x, y, cost;
x = R[i][0]; y = R[i][1];
cost = L[i];
v[x].push_back({y, cost});
v[y].push_back({x, cost});
}
for(i=0; i<N; ++i) best[i].resize(2, 2e9);
for(i=0; i<K; ++i) heap.push({0, P[i]});
while(heap.size())
{
int node, cost;
tie(cost, node) = heap.top();
heap.pop();
if(used[node]) continue;
used[node] = 1;
dist[node] = cost;
if(node == 0) break;
for(auto it : v[node])
{
int x, l;
tie(x, l) = it;
if(used[x]) continue;
int curr_best = best[x][1];
best[x].push_back(dist[node] + l);
sort(best[x].begin(), best[x].end());
best[x].pop_back();
if(best[x][1] < curr_best)
heap.push({best[x][1], x});
}
}
return dist[0];
}
