#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> // weight must be ll
#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;
V<pair<int,int>> adj[N];
ll dp[N], bst[N];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
int n = N, m = M;
rep(i, 1, n, 1)
adj[i].clear();
rep(i, 0, M - 1, 1) {
int x = R[i][0] + 1, y = R[i][1] + 1;
int w = L[i];
adj[x].pb({ y, w });
adj[y].pb({ x, w });
}
priority_queue<pii, V<pii>, greater<pii>> pq;
rep(i, 1, n, 1)
dp[i] = bst[i] = (ll)1e18; // BIG INF
rep(i, 0, K - 1, 1)
dp[P[i] + 1] = bst[P[i] + 1] = 0;
rep(i, 0, K - 1, 1)
pq.push({ 0LL, P[i] + 1 });
while (!pq.empty()) {
auto it = pq.top();
pq.pop();
ll w = it.first;
int node = it.second;
if (w != dp[node])
continue;
for (auto bs : adj[node]) {
int i = bs.first;
ll val = bs.second;
ll cost = w + val;
if (cost < bst[i]) {
dp[i] = bst[i];
bst[i] = cost;
pq.push({ dp[i], i });
}
else if (cost < dp[i]) {
dp[i] = cost;
pq.push({ dp[i], i });
}
}
}
return (int)dp[1];
}
