///100 poena
#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
const int MAXN=100009,INF=2000000000;
vector<pair<int,int>> graf[MAXN];
int prvi[MAXN],drugi[MAXN];
int rez[MAXN];
bool vi[MAXN];
int val(int node){
return drugi[node];
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
for(int i=0; i<N; i++) rez[i]=INF;
for(int i=0; i<M; i++){
int a=R[i][0],b=R[i][1],w=L[i];
graf[a].push_back({b,w});
graf[b].push_back({a,w});
}
for(int i=0; i<N; i++) prvi[i]=drugi[i]=INF;
priority_queue<pair<int,int>> red;
for(int i=0; i<K; i++) red.push({0,P[i]});
while(red.size()){
int node=red.top().second,tr=-red.top().first;
red.pop();
if(vi[node]) continue;
vi[node]=true;
rez[node]=tr;
for(auto x:graf[node]){
int nw=rez[node]+x.second;
if(nw<=prvi[x.first]){drugi[x.first]=prvi[x.first];prvi[x.first]=nw;continue;}
if(nw<=drugi[x.first]){drugi[x.first]=nw; continue;}
}
for(auto x:graf[node])
red.push({-val(x.first),x.first});
}
return rez[0];
}
