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