#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<pair<int, int>> g[N];
for(int i = 0; i < M; i ++){
g[R[i][0]].push_back({R[i][1], L[i]});
g[R[i][1]].push_back({R[i][0], L[i]});
}
priority_queue<pair<int, int>> q;
vector<int> mn1(N, INT_MAX);
vector<int> mn2(N, INT_MAX);
for(int i = 0; i < K; i ++){
mn1[P[i]] = mn2[P[i]] = 0;
q.push({0, P[i]});
}
vector<int> used(N, 0);
while(!q.empty()){
int v = q.top().second;
q.pop();
if(used[v] == 1) continue;
used[v] = 1;
for(auto to: g[v]){
if(mn1[to.first] >= mn2[v] + to.second){
mn2[to.first] = mn1[to.first];
mn1[to.first] = mn2[v] + to.second;
q.push({-mn2[to.first], to.first});
}
else if(mn2[to.first] > mn2[v] + to.second){
mn2[to.first] = mn2[v] + to.second;
q.push({-mn2[to.first], to.first});
}
}
}
return mn2[0];
}
