#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, ll>
#define pll pair<ll, ll>
#define V vector
#define V2dll V<V<ll>>
#define V2dchar V<V<char>>
#define V2dbool V<V<bool>>
#define V3dll V<V<V<ll>>>
#define V3dchar V<V<V<char>>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define FASTIO \
ios_base::sync_with_stdio(false); \
cin.tie(nullptr); \
cout.tie(nullptr);
#define INF ll_MAX
#define blt __builtin_popcount
#define clr(x) x.clear()
#define ff first
#define ss second
#define popf pop_front
#define popb pop_back
#define sz(x) ll(x.size())
#define rep(a, b, c, d) for (ll a = b; a <= c; a += d)
#define repl(a, b, c, d) for (ll a = b; a >= c; a -= d)
const ll N = 1e6 + 5;
V<pll> adj[N];
ll dp[N], bst[N];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
ll n = N, m = M;
rep(i, 0, M - 1, 1) {
ll x = R[i][0] + 1, y = R[i][1] + 1;
ll w = L[i];
adj[x].pb({ y, w });
adj[y].pb({ x, w });
}
priority_queue<pii, V<pii>, greater<pii>> pq;
function<void(ll)> update = [&](ll node) -> void {
ll w = dp[node];
//cout << node << " " << dp[node] << endl;
for (auto bs : adj[node]) {
ll i = bs.ff, val = bs.ss;
if (w + val < dp[i]) {
if (w + val < bst[i]) {
dp[i] = bst[i];
bst[i] = w + val;
}
else {
dp[i] = w + val;
}
if (dp[i] < 1e9)
pq.push({ dp[i], i });
}
}
return;
};
rep(i, 1, n, 1) {
dp[i] = bst[i] = 1e17;
}
rep(i, 0, K - 1, 1)
dp[P[i] + 1] = 0, bst[P[i] + 1] = 0;
rep(i, 0, K - 1, 1)
pq.push({ 0, P[i] + 1 });
while (!pq.empty()) {
auto it = pq.top();
pq.pop();
ll w = it.ff;
ll node = it.ss;
if (w != dp[node])
continue;
update(node);
}
return (int)dp[1];
}
