#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
int dp[N][2];
for (int i = 0; i < N; i++) {
dp[i][0] = dp[i][1] = INT_MAX;
}
vector <vector <pair<int,int>>> v(N);
for (int i = 0; i < M; i++) {
int u = R[i][0];
int u1 = R[i][1];
v[u].emplace_back(u1,L[i]);
v[u1].emplace_back(u,L[i]);
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
for (int i = 0; i < K; i++) {
dp[P[i]][0] = dp[P[i]][1] = 0;
q.push({0,P[i]});
}
while (!q.empty()) {
auto [w1,f] = q.top();
q.pop();
if (w1 > dp[f][1]) continue;
for (auto [to,w]:v[f]) {
if (dp[to][0] > w1 + w) {
if (dp[to][1] > dp[to][0]) {
dp[to][0] = dp[to][1];
q.push({dp[to][1],to});
}
dp[to][0] = w1 + w;
} else if (dp[to][1] > w1 + w) {
dp[to][1] = w1 + w;
q.push({dp[to][1],to});
}
}
}
return dp[0][1];
}
