#include "crocodile.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int QK=1e5+100,inf=1e9;
int n,k;
ll dist[QK],sp[QK];
ll dp[QK][5];
bool vis[QK];
vector<pair<int,int>> adj[QK];
void dykstra(){
for(int i=0;i<=n;i++)
{
dp[i][0]=inf;
dp[i][1]=inf;
dist[i]=inf;
}
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
for(int j=0;j<k;j++){
dist[sp[j]]=0;
pq.push({0,sp[j]});
}
while(!pq.empty()){
auto [d,u]=pq.top();pq.pop();
if(d>dist[u])continue;
for(auto [v,w]:adj[u]){
if(dist[v]>dist[u]+w){
dist[v]=dist[u]+w;
pq.push({dist[v],v});
}
}
}
}
void calculate(){
// dp[u] = answer if we start at u
//
// ord of {(dist,node)}
// dp[node][0] = min(dist[nei][0])
// dp[node][1] = 2min(dist[nei][0])
// vector<pair<ll,int>> ord;
// for(int i=0;i<n;i++)
// ord.push_back({dist[i],i});
// for(int i=0;i<5;i++)
// {
// sort(ord.begin(),ord.end());
// for(auto [d,u]:ord){
// auto it=lower_bound(sp,sp+k,u);
// if(it!=sp+k && *it==u){
// dp[u][0]=0;
// continue;
// }
// vector<ll> curp;
// for(auto [v,w]:adj[u]){
// curp.push_back(dp[v][0]+w);
// }
// sort(begin(curp),end(curp));
// dp[u][0]=min(dp[u][0],curp[1]);
// }
// ord.clear();
// for(int i=0;i<n;i++)
// {
// ord.push_back({dp[i][0],i});
// }
// // sort(begin())
// }
set<int> cur;
for(int i=0;i<k;i++)
{
dp[sp[i]][0]=0;
vis[sp[i]]=1;
for(auto [u,w]:adj[sp[i]])
{
if(!vis[u])
{
vis[u]=1;
cur.insert(u);
}
}
}
while(cur.size())
{
set<int> curp;
vector<pair<ll,ll>> ord;
for(auto x:cur)
{
vector<ll> curp;
for(auto [v,w]:adj[x]){
curp.push_back(dp[v][0]+w);
}
sort(begin(curp),end(curp));
dp[x][0]=min(dp[x][0],curp[1]);
// cout<<"At "<<x<<' '<<dp[x][0]<<endl;;
ord.push_back({dp[x][0],x});
}
sort(begin(ord),end(ord));
for(auto [asdpo,x]:ord)
{
vector<ll> curp;
for(auto [v,w]:adj[x]){
curp.push_back(dp[v][0]+w);
}
sort(begin(curp),end(curp));
dp[x][0]=min(dp[x][0],curp[1]);
ord.push_back({dp[x][0],x});
}
for(auto x:cur)
{
vis[x]=1;
for(auto [u,w]:adj[x])
{
if(!vis[u])
{
vis[u]=1;
curp.insert(u);
}
}
}
cur=curp;
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
n=N,k=K;
for(int i=0;i<K;i++)
sp[i]=P[i];
// sort(sp,sp+K);
for(int i=0;i<M;i++){
int u=R[i][0],v=R[i][1],l=L[i];
adj[u].push_back({v,l});
adj[v].push_back({u,l});
}
dykstra();
calculate();
return dp[0][0];
}
