#include <bits/stdc++.h>
#include "crocodile.h"
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
using namespace std;
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout */
const ll INF = 1e15;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<vector<pair<ll,ll>>> adj(N+1);
for(ll i = 0 ; i < M ; i++){
adj[R[i][0]].pb({R[i][1],L[i]});
adj[R[i][1]].pb({R[i][0],L[i]});
}
priority_queue<pair<ll,ll>, vector<pair<ll,ll>>, greater<pair<ll,ll>>> pq;
vector<pair<ll,ll>> dist(N+1);
for(ll i = 0 ; i < N ; i++){
dist[i] = {INF,INF};
}
for(ll i = 0 ; i < K ; i++){
pq.push({0,P[i]});
dist[P[i]] = {0,INF};
}
while(!pq.empty()){
ll node = pq.top().second;
ll weight = pq.top().first;
pq.pop();
if(weight > dist[node].second) continue;
if(weight < dist[node].first){
dist[node] = {weight,dist[node].first};
for(auto go : adj[node]){
pq.push({dist[node].second + go.second,go.first});
}
}else{
dist[node].second = weight;
for(auto go : adj[node]){
pq.push({dist[node].second + go.second,go.first});
}
}
}
return dist[0].second;
}
