#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 4e18;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<pair<int, ll>> adj[N];
for(int i = 0;i<M;i++){
adj[R[i][0]].push_back({R[i][1], L[i]});
adj[R[i][1]].push_back({R[i][0], L[i]});
}
vector<ll> mn(N, INF), smn(N, INF);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
for(int i = 0;i<K;i++){
mn[P[i]] = smn[P[i]] = 0;
pq.push({0, P[i]});
}
while(!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if(d > smn[u]) continue;
for(auto [v, w] : adj[u]){
bool f = 0;
if(d + w < mn[v]){
if(mn[v] != smn[v] && mn[v] != INF){
smn[v] = mn[v];
f = 1;
}
mn[v] = d + w;
}else if(d + w < smn[v]){
smn[v] = d + w;
f = 1;
}
if(f) pq.push({smn[v], v});
}
}
return (int)smn[0];
}
