#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define oo 1e18
const int MAX = 1e5 + 5;
int n, m;
vector<int> esc;
vector<pii> g[MAX];
ll dp[MAX][2];
void djikstra(){
for(int i = 0; i < n; i++){
dp[i][0] = oo;
dp[i][1] = oo;
}
set<pii> s;
for(int e : esc){
dp[e][0] = 0;
dp[e][1] = 0;
s.insert({0, e});
}
while(s.size()){
int a = s.begin()->second;
s.erase(s.begin());
for(pii to : g[a]){
ll nw = dp[a][1] + to.second;
if(dp[to.first][0] <= nw){
if(dp[to.first][1] > nw){
s.erase({dp[to.first][1], to.first});
dp[to.first][1] = nw;
s.insert({dp[to.first][1], to.first});
}
}
else{
s.erase({dp[to.first][1], to.first});
dp[to.first][1] = dp[to.first][0];
s.insert({dp[to.first][1], to.first});
dp[to.first][0] = nw;
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
n = N, m = M;
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]});
}
for(int i = 0; i < K; i++){
esc.push_back(P[i]);
}
djikstra();
return dp[0][1];
}
