#include "crocodile.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair <ll,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 <ll> d1(N+5,INF);
vector <vector <pii>> adj(N+5);
vector <bool> 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({d1[P[i]]=0,P[i]});
}
//return -3;
while(!pq.empty()){
auto [d_u,u]=pq.top();
pq.pop();
if(d_u>d1[u]) continue;
for(auto [v,w]:adj[u]) if(d1[v]>d_u+w) pq.push({d1[v]=d_u+w,v});
}
//return -2;
vector <ll> d2(N+5,INF);
pq.push({d2[0]=0,0});
while(!pq.empty()){
auto [d_u,u]=pq.top();
pq.pop();
if(en[u]) return d_u;
if(d_u>d2[u]) continue;
int idx=-1,mn=INF;
for(auto [v,w]:adj[u]) if(d1[v]<mn) mn=d1[v],idx=v;
for(auto [v,w]:adj[u]) if(v!=idx && d2[v]>d_u+w) pq.push({d2[v]=d_u+w,v});
}
return -1;
}
