#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dist1[100005];
ll dist2[100005];
bool ext[100005];
const int MX = 1000000007;
int n;
vector <pair <int, ll>> graf[100005];
set <pair <ll, int>> q;
void sp(){
for(int i=1; i<=n; i++){
if(ext[i]) dist2[i] = 0;
else dist2[i] = MX;
dist1[i] = dist2[i];
q.insert({dist2[i], i});
}
while(!q.empty()){
int v = q.begin()->second;
q.erase(q.begin());
if(v == 1) return;
for(auto pr : graf[v]){
int c = pr.first;
int dis = pr.second+dist2[v];
if(dis < dist1[c]){
q.erase({dist2[c], c});
dist2[c] = dist1[c];
dist1[c] = dis;
q.insert({dist2[c], c});
}
else if(dis < dist2[c]){
q.erase({dist2[c], c});
dist2[c] = dis;
q.insert({dist2[c], c});
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
n = N;
int m = M;
int k = K;
for(int i=0; i<m; i++){
R[i][0]++;
R[i][1]++;
graf[R[i][0]].push_back({R[i][1], L[i]});
graf[R[i][1]].push_back({R[i][0], L[i]});
}
for(int i=0; i<k; i++){
P[i]++;
ext[P[i]] = 1;
}
sp();
return dist2[1];
}
