#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 NMAX = 100005;
const ll INF = LLONG_MAX / 4;
V<pii> adj[NMAX];
ll dp[NMAX], bst[NMAX];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
// IMPORTANT: clear graph (IOI calls multiple times)
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].pb({y, w});
adj[y].pb({x, w});
}
// Initialize
for (int i = 1; i <= N; i++) {
bst[i] = INF; // shortest
dp[i] = INF; // second shortest
}
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
// Multi-source start
for (int i = 0; i < K; i++) {
int node = P[i] + 1;
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, val] : adj[node]) {
ll new_dist = w + val;
if (new_dist < bst[to]) {
dp[to] = bst[to];
bst[to] = new_dist;
pq.push({new_dist, to});
}
else if (new_dist > bst[to] && new_dist < dp[to]) {
dp[to] = new_dist;
pq.push({new_dist, to});
}
}
}
return (int)dp[1]; // guaranteed ≤ 1e9
}
