#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
const int NN = 1e5 + 10;
#define ll long long
vector<pair<int, ll>> adj[NN];
ll dp[NN][2];
bool ka[NN];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for (int i = 0; i < M; i++) {
adj[R[i][0]].push_back({ R[i][1], L[i] });
adj[R[i][1]].push_back({ R[i][0], L[i] });
}
for (int i = 0; i < K; i++) ka[P[i]] = 1;
for (int i = 0; i < N; i++) {
dp[i][0] = dp[i][1] = INT64_MAX;
}
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>pq;
for(int i = 0; i < K; i++){
pq.push({ 0, P[i] });
dp[P[i]][0] = dp[P[i]][1] = 0;
}
while (!pq.empty()) {
auto [d, node] = pq.top();
pq.pop();
if (d != dp[node][1]) continue;
for (auto [u, w] : adj[node]) {
if (dp[node][1] + w < dp[u][0]) {
dp[u][1] = dp[u][0];
dp[u][0] = dp[node][1] + w;
if (dp[u][1] != INT64_MAX) {
pq.push({ dp[u][1], u });
}
}
else if (dp[node][1] + w < dp[u][1]) {
dp[u][1] = dp[node][1] + w;
pq.push({ dp[u][1], u });
}
}
}
return dp[0][1];
}
