#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
using ll = long long;
const int N=1e5;
const ll inf=1e18;
pair<ll,ll> dp[N];
vector<pair<int,int>>graph[N];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
for(int i=0;i<N;++i)
dp[i]={inf,inf};
int u,v;
for(int i=0;i<M;++i){
u=R[i][0];v=R[i][1];
graph[u].push_back({v,L[i]});
graph[v].push_back({u,L[i]});
}
priority_queue<pair<int,ll>,vector<pair<int,ll>>,greater<>>q;
for(int i=0;i<K;++i){
u=P[i];
dp[u]={0,0};
q.push({u,0});
}
ll w;
while(!q.empty()){
u=q.top().first;
w=q.top().second;
q.pop();
for(auto&i:graph[u]){
v=i.first;
bool ok=0;
if(dp[v].first>=w+i.second){
dp[v].second=dp[v].first;
dp[v].first=w+i.second;
ok=1;
}
else if(dp[v].second>w+i.second){
dp[v].second=w+i.second;
ok=1;
}
if(ok)q.push({v,dp[v].second});
}
}
return dp[0].second;
}
