#include "crocodile.h"
#include <vector>
#include <queue>
#include <array>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
vector<vector<pair<int, long long>>> adj(N);
for(int i{}; 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]});
}
priority_queue<pair<long long, int>,
vector<pair<long long, int>>,
greater<pair<long long, int>>> pq;
vector<long long> dist(N, -1);
vector<int> processed_neighbours(N);
vector<array<long long, 2>> paths(N);
vector<bool> processed(N);
for(int i{}; i < K; ++i)
dist[P[i]] = 0, pq.push({0, P[i]});
auto update = [&](int u, long long d) {
if(processed[u]) return;
switch(processed_neighbours[u]) {
case 0:
paths[u][0] = d;
break;
case 1:
paths[u][1] = d;
if(paths[u][1] < paths[u][0])
swap(paths[u][1], paths[u][0]);
pq.push({paths[u][1], u});
break;
default:
if(d < paths[u][1])
paths[u][1] = d;
if(paths[u][1] < paths[u][0])
swap(paths[u][1], paths[u][0]);
pq.push({paths[u][1], u});
break;
}
++processed_neighbours[u];
};
while(!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if(processed[u])
continue;
processed[u] = true;
dist[u] = d;
for(auto [v, w]: adj[u])
update(v, d + w);
}
return int(dist[0]);
}
