#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define sort_uniq(x) sort(all(x)), uniq(x);
#define ll long long
#define ld long double
#define pii pair<ll,int>
#define pll pair<int,int>
#define V vector
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define sz(x) int(x.size())
#define rep(a,b,c,d) for (int a=b; a<=c; a+=d)
const int N = 1e5 + 5;
const ll INF = (ll)1e18;
V<pair<int,int>> adj[N];
ll dp[N], bst[N];
int travel_plan(int Nn, int M, int R[][2], int L[], int K, int P[])
{
int n = Nn;
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});
}
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 v = P[i] + 1;
bst[v] = 0;
dp[v] = 0;
pq.push({0LL, v});
}
while(!pq.empty()) {
auto [w, node] = pq.top();
pq.pop();
if(w > dp[node]) continue;
for(auto bs : adj[node]) {
int to = bs.first;
ll cost = w + bs.second;
if(cost < bst[to]) {
dp[to] = bst[to];
bst[to] = cost;
pq.push({bst[to], to});
if(dp[to] < INF)
pq.push({dp[to], to});
}
else if(cost > bst[to] && cost < dp[to]) {
dp[to] = cost;
pq.push({dp[to], to});
}
}
}
return (int)dp[1];
}
