#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, ll>
#define V vector
#define ff first
#define ss second
#define pb push_back
#define rep(a, b, c, d) for (int a = b; a <= c; a += d)
const int MAXN = 1e5 + 5;
const ll INF = LLONG_MAX / 4;
V<pii> adj[MAXN];
ll dp[MAXN], bst[MAXN];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
int n = N;
// Build graph
rep(i, 0, M - 1, 1) {
int x = R[i][0] + 1;
int y = R[i][1] + 1;
ll w = (ll)L[i];
adj[x].pb({y, w});
adj[y].pb({x, w});
}
// Initialize distances
rep(i, 1, n, 1) {
dp[i] = INF;
bst[i] = INF;
}
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
// Start from all safe nodes
rep(i, 0, K - 1, 1) {
int node = P[i] + 1;
dp[node] = 0;
bst[node] = 0;
pq.push({0, node});
}
// Modified Dijkstra
while (!pq.empty()) {
auto [w, node] = pq.top();
pq.pop();
if (w != dp[node]) continue;
for (auto [to, weight] : adj[node]) {
ll new_dist = w + weight;
if (new_dist < dp[to]) {
if (new_dist < bst[to]) {
dp[to] = bst[to];
bst[to] = new_dist;
} else {
dp[to] = new_dist;
}
if (dp[to] < INF)
pq.push({dp[to], to});
}
}
}
return (int)dp[1]; // problem expects int
}
