#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
const ll INF = 1e18;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
vector<vector<pair<int, ll>>> adj(N);
for (int i = 0; i < M; i++) {
auto &[u, v] = R[i];
adj[u].emplace_back(v, L[i]);
adj[v].emplace_back(u, L[i]);
}
using state = tuple<ll, int>;
vector<ll> dist(N, INF), cnt(N, 0);
priority_queue<state, vector<state>, greater<state>> pq;
for (int i = 0; i < K; i++) {
dist[P[i]] = 0;
pq.emplace(0, P[i]);
pq.emplace(0, P[i]);
}
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
// cerr << u sp d << endl;
if (d > dist[u]) continue;
if (cnt[u] < 1) {
cnt[u]++;
continue;
}
dist[u] = d;
for (auto &[v, w] : adj[u]) {
if (dist[u] + w < dist[v]) {
pq.emplace(dist[u] + w, v);
}
}
}
// for (int i = 0; i < N; i++) {
// cerr << (dist[i] == INF ? -1 : dist[i]) << " ";
// } cerr << endl;
return dist[0];
}
