#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define V vector
#define pb push_back
#define ff first
#define ss second
#define rep(a,b,c,d) for(int a=b;a<=c;a+=d)
const int N = 1e5 + 5;
const int INF = 1e9;
V<pii> adj[N];
int dp[N], bst[N];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
rep(i,1,N,1) adj[i].clear();
rep(i,0,M-1,1){
int x = R[i][0] + 1;
int y = R[i][1] + 1;
int w = L[i];
adj[x].pb({y,w});
adj[y].pb({x,w});
}
// Initialize
rep(i,1,N,1)
dp[i] = bst[i] = INF;
priority_queue<pii, V<pii>, greater<pii>> pq;
rep(i,0,K-1,1){
int node = P[i] + 1;
bst[node] = 0;
dp[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]){
int new_dist = w + val;
if(new_dist < bst[to]){
dp[to] = bst[to];
bst[to] = new_dist;
pq.push({bst[to], to});
}
else if(new_dist > bst[to] && new_dist < dp[to]){
dp[to] = new_dist;
pq.push({dp[to], to});
}
}
}
return dp[1];
}
