#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
#define fr first
#define sc second
#define pb emplace_back
const int mxN = 1005;
vector<pi> adj[mxN];
const ll inf = 1e15;
// work backwards maybe?
// start from the exit nodes
// dp[i] = 2nd max of all the nodes we can come from
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]].pb(R[i][1], L[i]);
adj[R[i][1]].pb(R[i][0], L[i]);
}
priority_queue<pi> pq;
ll dist[N][2] = {};
bool vis[N] = {};
for(int i = 0; i < N; ++i) {
dist[i][1] = dist[i][0] = inf;
}
for(int i = 0; i < K; ++i) {
dist[P[i]][1] = dist[P[i]][0] = 0;
pq.emplace(0, P[i]);
}
while(!pq.empty()) {
ll x = pq.top().sc;
pq.pop();
if(vis[x]) continue;
vis[x] = true;
for(auto [y, w] : adj[x]) {
ll curr = dist[x][1] + w;
if(dist[y][0] >= curr) {
dist[y][1] = dist[y][0];
dist[y][0] = curr;
pq.emplace(-dist[y][1], y);
} else if(dist[y][1] > curr) {
dist[y][1] = curr;
pq.emplace(-dist[y][1], y);
}
}
}
return dist[0][1];
}
