#include "crocodile.h"
#include <bits/stdc++.h>
#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define uset unordered_set
#define umap unordered_map
#define pqueue priority_queue
using namespace std;
struct res {
ll i, sum;
};
bool operator < (const res& i, const res& j) { return (i.sum > j.sum); }
vector<vector<pair<ll, ll>>> adj;
vector<pair<ll, ll>> memo;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
adj.resize(N);
memo.resize(N, {((ll) 1 << 60), ((ll) 1 << 60)});
range(i, 0, M) {
adj[R[i][0]].push_back({R[i][1], L[i]});
adj[R[i][1]].push_back({R[i][0], L[i]});
}
pqueue<res> pq;
range(i, 0, K) {
memo[P[i]].first = 0;
pq.push({P[i], 0});
}
res t;
vector<int> visited (N);
while (!pq.empty()) {
t = pq.top(); pq.pop();
ll sec = memo[t.i].second;
visited[t.i]++;
if (t.sum <= memo[t.i].first) {
memo[t.i].second = memo[t.i].first;
memo[t.i].first = t.sum;
}
else memo[t.i].second = min(memo[t.i].second, t.sum);
if (sec != memo[t.i].second) {
for (pair<ll, ll> k : adj[t.i]) {
if (visited[k.first] < 2) {
pq.push({k.first, memo[t.i].second + k.second});
}
}
}
}
return memo[0].second;
}
