#include "crocodile.h"
#include <bits/stdc++.h>
#define pii pair <int,int>
using namespace std;
const int INF=1e9+7;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
vector <int> d(N+5,INF);
vector <vector <pii>> adj(N+5);
vector <int> en(N+5,false);
priority_queue <pii,vector <pii>,greater <pii>> pq;
for(int i=0;i<M;i++){
adj[R[i][0]].push_back({R[i][1],L[i]});
adj[R[i][1]].push_back({R[i][0],L[i]});
}
for(int i=0;i<K;i++) en[P[i]]=true;
pq.push({d[0]=0,0});
while(!pq.empty()){
auto [d_u,u]=pq.top();
pq.pop();
if(en[u]){
return d_u;
}
if(d_u>d[u] || d_u>INF) continue;
int idx=-1,mn=INF;
for(auto [v,w]:adj[u]) if(d_u+w<d[v] && en[v] && d_u+w<mn) mn=d_u+w,idx=v;
if(idx==-1) for(auto [v,w]:adj[u]) if(d_u+w<d[v] && d_u+w<mn) mn=d_u+w,idx=v;
for(auto [v,w]:adj[u]){
if(v!=idx && d_u+w<d[v]){
pq.push({d[v]=d_u+w,v});
}
}
}
return -1;
}
