#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ar array
#define ll long long
const ll INF = 1e15;
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]) {
vector<ar<ll,2>> g[n];
for (ll i = 0; i < m; i++) {
g[R[i][0]].push_back({L[i], R[i][1]});
g[R[i][1]].push_back({L[i], R[i][0]});
}
vector<ll> d1(n, INF), d2(n, INF);
priority_queue<ar<ll,2>, vector<ar<ll,2>>, greater<ar<ll,2>>> pq;
for (ll i = 0; i < k; i++) pq.push({d1[P[i]] = d2[P[i]] = 0, P[i]});
while (!pq.empty()) {
ll u = pq.top()[1], dist = pq.top()[0]; pq.pop();
for (auto v : g[u]) {
if (dist + v[0] < d1[v[1]]) d2[v[1]] = d1[v[1]], d1[v[1]] = dist + v[0];
else if (dist + v[0] < d2[v[1]]) d2[v[1]] = dist + v[0];
else continue;
if (d2[v[1]] <= INF/2) pq.push({d2[v[1]], v[1]});
}
}
return d2[0];
}
