#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
vector<pair<int, int>> adj[N];
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]});
}
vector<int> dist(N, INT_MAX);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for(int i = 0;i<K;i++){
dist[P[i]] = 0;
pq.push({0, P[i]});
}
while(!pq.empty()){
auto [d, u] = pq.top();
pq.pop();
if(d > dist[u]) continue;
for(auto [v, w] : adj[u]){
if(d + w < dist[v]){
dist[v] = d + w;
pq.push({d + w, v});
}
}
}
int c = 0, ans = 0;
vector<bool> vis(N, 0);
while(dist[c] != 0){
vis[c] = 1;
pair<int, int> mn = {INT_MAX, 0}, smn = {INT_MAX, 0};
for(auto [v, w] : adj[c]){
if(vis[v]) continue;
if(dist[v] + w < mn.first){
smn = mn;
mn = {dist[v] + w, v};
}else if(dist[v] + w < smn.first){
smn = {dist[v] + w, v};
}
}
ans += smn.first - dist[smn.second];
c = smn.second;
}
return ans;
}
