#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
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[])
{
// 🔥 IMPORTANT: clear graph
for (int i = 1; i <= N; i++)
adj[i].clear();
// Build graph
for (int i = 0; i < M; i++) {
int x = R[i][0] + 1;
int y = R[i][1] + 1;
ll w = (ll)L[i];
adj[x].push_back({y, w});
adj[y].push_back({x, w});
}
// Initialize
for (int i = 1; i <= N; i++) {
dp[i] = INF;
bst[i] = INF;
}
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
// Start from safe nodes
for (int i = 0; i < K; i++) {
int node = P[i] + 1;
dp[node] = 0;
bst[node] = 0;
pq.push({0, node});
}
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;
}
pq.push({dp[to], to});
}
}
}
return (int)dp[1];
}
