#include <bits/stdc++.h>
using namespace std;
int i,node,sos,len,tg;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<pair<int,int>> adj[N];
int dist[N][2];
int prov[N];
for(i = 0; i < N; i++){
dist[i][0]=2000000000;
dist[i][1]=2000000000;
prov[i]=N;
}
for(i = 0; i <K; i++){
dist[P[i]][1]=0;
dist[P[i]][0]=0;
}
for(i = 0; i < M; i++){
adj[R[i][1]].push_back({R[i][0],L[i]});
adj[R[i][0]].push_back({R[i][1],L[i]});
}
priority_queue<pair<int,int>> pq;
for(int i = 0; i < K; i++)pq.push({0,P[i]});
while(!pq.empty()){
node = pq.top().second;
sos = 0-pq.top().first;
pq.pop();
for(auto x: adj[node]){
len = x.second;
tg = x.first;
//cout << "len " << len << " tg " << tg << "\n";
if(dist[tg][0]>sos+len){
prov[tg]=node;
dist[tg][1]=dist[tg][0];
dist[tg][0]=sos+len;
pq.push({0-dist[tg][1],tg});
}else if(dist[tg][1]>sos+len && prov[tg]!=node){
dist[tg][1]=sos+len;
pq.push({0-dist[tg][1],tg});
}
}
}
return dist[0][1];
}
