// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll cap = 1e6 + 1;
vector<pair<ll,ll>> adj[cap];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
for (ll i = 0; i < N; i++) adj[i].clear();
for (ll i = 0; i < M; i++) {
ll a = R[i][0];
ll b = R[i][1];
ll w = L[i];
adj[a].push_back({b, w});
adj[b].push_back({a, w});
}
priority_queue<pair<ll,ll>> pq;
vector<ll> dp(N, -1);
vector<ll> cnt(N, 0);
for (ll i = 0; i < K; i++) {
ll a = P[i];
cnt[a] = 1;
dp[a] = 0;
pq.push({0, a});
}
while (!pq.empty()) {
auto top = pq.top(); pq.pop();
ll dist = -top.first;
ll u = top.second;
if (cnt[u] == 2) continue;
cnt[u]++;
if (cnt[u] == 1) continue;
dp[u] = dist;
for (auto [v, w] : adj[u]) {
if (cnt[v] < 2) {
pq.push({-(dist + w), v});
}
}
}
return dp[0];
}
