#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
const int MAX_N = 1e5 + 10;
const int INF = 1e9 + 7;
int dist1[MAX_N], dist2[MAX_N];
vector <pair <int, int>> adj[MAX_N];
bool visited[MAX_N];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
for(int i = 1; i <= N; i++) {
dist1[i] = dist2[i] = INF;
}
for(int i = 0; i < M; i++) {
R[i][0]++, R[i][1]++;
adj[R[i][0]].emplace_back(R[i][1], L[i]);
adj[R[i][1]].emplace_back(R[i][0], L[i]);
}
priority_queue <pair <int, int>> pq;
for(int i = 0; i < K; i++) {
P[i]++;
dist1[P[i]] = dist2[P[i]] = 0;
pq.emplace(0, P[i]);
}
while(!pq.empty()) {
int u = pq.top().second;
pq.pop();
if(visited[u] == true) {
continue;
}
visited[u] = true;
for(auto [v, w] : adj[u]) {
if(visited[v] == true) {
continue;
}
if(dist2[u] + w <= dist1[v]) {
dist2[v] = dist1[v];
dist1[v] = dist2[u] + w;
}
else if(dist2[u] + w < dist2[v]) {
dist2[v] = dist2[u] + w;
}
if(dist2[v] != INF) {
pq.emplace(-dist2[v], v);
}
}
}
return dist2[1];
}
