#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<ll, ll>
using namespace std;
const ll inf = 1e18;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
vector<pii> adj[N];
ll dis[2][N];
for (int i = 0; i < N; i++) dis[0][i] = dis[1][i] = inf;
for (int i = 0; i < M; i++) {
int u = R[i][0], v = R[i][1];
adj[u].emplace_back(L[i], v);
adj[v].emplace_back(L[i], u);
}
priority_queue<pii, vector<pii>, greater<pii>> q;
for (int i = 0; i < K; i++) dis[0][P[i]] = dis[1][P[i]] = 0, q.emplace(0, P[i]);
while (!q.empty()) {
auto [w, u] = q.top();
q.pop();
if (w > dis[1][u] || w == inf) continue;
for (auto &[ww, v] : adj[u]) {
if (ww + w < dis[0][v]) dis[1][v] = dis[0][v], dis[0][v] = ww + w, q.emplace(dis[1][v], v);
else if (ww + w < dis[1][v]) dis[1][v] = ww + w, q.emplace(dis[1][v], v);
}
}
return (int)dis[1][0];
}
