#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int MAXN = 1e5 + 5;
const int oo = 1e9 + 1;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
vector<vector<pii>> adj(N);
for (int i = 0; i < M; i++) {
int x = R[i][0];
int y = R[i][1];
int z = L[i];
adj[x].push_back({z, y});
adj[y].push_back({z, x});
}
vector<vector<int>> d(N, vector<int>(2, oo));
priority_queue<pii, vector<pii>, greater<pii>> pq;
for (int i = 0; i < K; i++) {
d[P[i]][0] = 0;
d[P[i]][1] = 0;
pq.push({0, P[i]});
}
while (!pq.empty()) {
int dist = pq.top().X;
int u = pq.top().Y;
pq.pop();
if (dist > d[u][1]) continue;
for (auto &edge : adj[u]) {
int w = edge.X;
int v = edge.Y;
int new_dist = dist + w;
if (d[v][0] > new_dist) {
if (d[v][1] != d[v][0]) {
d[v][1] = d[v][0];
pq.push({d[v][1], v});
}
d[v][0] = new_dist;
}
else if (d[v][1] > new_dist) {
d[v][1] = new_dist;
pq.push({d[v][1], v});
}
}
}
return d[0][1];
}
