#include "crocodile.h"
#include "bits/stdc++.h"
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
vector<vector<pair<int, int>>> g(N);
for (int i = 0; i < M; ++i) {
g[R[i][0]].emplace_back(R[i][1], L[i]);
g[R[i][1]].emplace_back(R[i][0], L[i]);
}
const int INF = 1e9;
vector<vector<int>> dis(N, vector<int> (2, INF));
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (int i = 0; i < K; ++i) {
dis[P[i]][0] = dis[P[i]][1] = 0;
pq.emplace(0, P[i]);
}
while (!pq.empty()) {
auto [c, v] = pq.top();
pq.pop();
if (c != dis[v][1]) {
continue;
}
for (auto [u, w] : g[v]) {
int nc = c + w;
if (nc < dis[u][1]) {
dis[u][1] = nc;
if (dis[u][0] > dis[u][1]) {
swap(dis[u][0], dis[u][1]);
}
if (dis[u][1] != INF) {
pq.emplace(dis[u][1], u);
}
}
}
}
return dis[0][1];
}
