#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> dist1(N, INF), dist2(N, INF);
priority_queue<state, vector<state>, greater<state>> pq;
for (int i = 0; i < K; i++) {
dist1[P[i]] = 0;
dist2[P[i]] = 0;
pq.emplace(0, P[i]);
}
vector<bool> vis(N, false);
while (!pq.empty()) {
auto [d, u] = pq.top(); pq.pop();
if (d > dist2[u]) continue;
if (vis[u]) continue; // don't over-propagate
vis[u] = true;
for (auto &[v, w] : adj[u]) {
ll n = d + w;
if (n < dist1[v]) {
dist2[v] = dist1[v];
dist1[v] = n;
pq.emplace(dist2[v], v);
} else if (n < dist2[v]) {
dist2[v] = n;
pq.emplace(dist2[v], v);
}
}
}
return dist2[0];
}
