#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
struct arbore{
int nod,cost;
bool operator>(const arbore & o)const{
return cost > o.cost;
}
};
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
vector<vector<arbore>>tabel(N+1);
vector<vector<int>>dp(N+1,vector<int>(2,1e9+1));
for(int i=0;i<M;i++){
tabel[R[i][0]].push_back({R[i][1],L[i]});
tabel[R[i][1]].push_back({R[i][0],L[i]});
}
priority_queue<arbore,vector<arbore>,greater<arbore>>pq;
for(int i=0;i<K;i++){
pq.push({P[i],0});
dp[P[i]] = {0,0};
}
while(!pq.empty()){
auto curent = pq.top();
pq.pop();
if(dp[curent.nod][1] < curent.cost)
continue;
for(auto i : tabel[curent.nod]){
if(curent.cost + i.cost < dp[i.nod][0]){
if(dp[i.nod][0] <= 1e9)
pq.push({i.nod,dp[i.nod][0]});///practic am mai gasit unu bun
dp[i.nod][1] = dp[i.nod][0];
dp[i.nod][0] = curent.cost + i.cost;
}
else
if(curent.cost + i.cost < dp[i.nod][1]){
dp[i.nod][1] = curent.cost + i.cost;
pq.push({i.nod,dp[i.nod][1]});
}
}
}
return dp[0][1];
}
