#include<bits/stdc++.h>
#define ll long long
#include "crocodile.h"
#define INF 987654321987654321ll
using namespace std;
priority_queue<pair<ll,ll> >pq;
vector<ll>cg[100005],cv[100005];
ll n,m,k,p[100005],cval,cidx;
ll mn[100005][2];
bool vis[100005];
bool update(ll idx,ll val) {
if(mn[idx][0]>val) {
mn[idx][1]=mn[idx][0];
mn[idx][0]=val;
return true;
}
if(mn[idx][1]>val) {
mn[idx][1]=val;
return true;
}
return false;
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
ll i; n=N; m=M; k=K;
for(i=0;i<n;i++) {
mn[i][0]=INF;
mn[i][1]=INF;
}
for(i=0;i<k;i++) {
p[i]=P[i];
mn[p[i]][0]=mn[p[i]][1]=0;
pq.push({0,p[i]});
}
for(i=0;i<m;i++) {
cg[R[i][0]].push_back(R[i][1]);
cv[R[i][0]].push_back(L[i]);
cg[R[i][1]].push_back(R[i][0]);
cv[R[i][1]].push_back(L[i]);
}
while(!pq.empty()) {
cval=-pq.top().first;
cidx=pq.top().second;
pq.pop();
if(vis[cidx])continue;
vis[cidx]=true;
for(i=0;i<cg[cidx].size();i++) {
if(!vis[cg[cidx][i]] && update(cg[cidx][i],cv[cidx][i]+cval) && mn[cg[cidx][i]][1]!=INF) {
pq.push({-mn[cg[cidx][i]][1],cg[cidx][i]});
}
}
}
return mn[0][1];
}
