#include<bits/stdc++.h>
#include "crocodile.h"
using namespace std;
using ll = long long;
const int n=1e5+5;
const ll inf=1e18;
struct cost{
ll mn1,mn2;
cost(ll a=inf,ll b=inf){
mn1=a;
mn2=b;
}
void add(ll x){
if(mn1>=x){
mn2=mn1;
mn1=x;
}
else if(mn2>=x)mn2=x;
}
bool operator<(const cost b) const{
if(mn2==b.mn2)return mn1<b.mn1;
return mn2<b.mn2;
}
};
vector<cost>dp(n);
vector<pair<int,int>>graph[n];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
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<cost,int>,vector<pair<cost,int>>,greater<pair<cost,int>>>q;
for(int i=0;i<K;++i){
u=P[i];
dp[u]={0,0};
q.push({dp[u],u});
}
bool vis[n+1];
ll w;
while(!q.empty()){
u=q.top().second;
w=q.top().first.mn2;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto&i:graph[u]){
v=i.first;
cost cur=dp[v];
cur.add(i.second+dp[u].mn2);
if(cur<dp[v]){
dp[v]=cur;
q.push({dp[v],v});
}
}
}
return dp[0].mn2;
}
