#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<pair<int, int>> G[N+5];
//<to, cost>
vector<int> block(N+5, -1);
vector<bool> odw(N+5, 0);
priority_queue<pair<long long, pair<int, int>>> PQ;
//<-cost>,<from, to>
for(int i=0; i<M; i++){
G[R[i][0]].push_back({R[i][1], L[i]});
G[R[i][1]].push_back({R[i][0], L[i]});
}
/////////
for(int i=0; i<K; i++){
int e = P[i];
odw[e] = 1;
}
for(int i=0; i<K; i++){
int e = P[i];
for(int j=0; j<G[e].size(); j++){
if(!odw[G[e][j].first]){
PQ.push({-G[e][j].second, {e, G[e][j].first}});
//cout << G[e][j].second << ' ' << e << ' ' << G[e][j].first << '\n';
}
}
}
while(!PQ.empty()){
long long cost = -PQ.top().first;
int from = PQ.top().second.first;
int to = PQ.top().second.second;
//cout << "go " << cost << ' ' << from << ' ' << to << '\n';
if(block[to] == -1){
block[to] = from;
}else if(block[to] != from){
if(!odw[to]){
if(to == 0){
return cost;
}
odw[to] = 1;
for(int i=0; i<G[to].size(); i++){
pair<int, int> s = G[to][i];
if(!odw[s.first]){
PQ.push({-(cost+s.second), {to, s.first}});
//cout << "add " << cost+s.second << ' ' << to << ' ' << s.first << '\n';
}
}
}
}
PQ.pop();
}
return 0;
}
