#include <bits/stdc++.h>
#include "crocodile.h"
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, ll> pii;
struct ura{
int inicio, destino;
ll peso;
const bool operator < (const ura & a) const {
return peso > a.peso;
}
};
priority_queue<ura> pq;
bool salidas[100002];
bool primer_camino[100002];
ll respuesta[100002];
vector<pii> graph[100002];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
forn(i, 0, N - 1){
salidas[i] = 0;
primer_camino[i] = 0;
respuesta[i] = 0LL;
}
forn(i, 0, M - 1){
graph[R[i][0]].pb(mp(R[i][1], (ll) L[i]));
graph[R[i][1]].pb(mp(R[i][0], (ll) L[i]));
}
forn(i, 0, K - 1){
primer_camino[P[i]] = 1;
salidas[P[i]] = 1;
for(pii u : graph[P[i]]){
pq.push({P[i], u.fi, u.se});
}
}
while(!pq.empty()){
ura act = pq.top();
pq.pop();
if(salidas[act.destino]){
continue;
}
if(!primer_camino[act.destino]){
primer_camino[act.destino] = 1;
continue;
}
salidas[act.destino] = 1;
respuesta[act.destino] = act.peso;
for(pii u : graph[act.destino]){
pq.push({act.destino, u.fi, act.peso + u.se});
}
}
return (int) respuesta[0];
}
