#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define fir first
#define sec second
const int maxn=1e5;
const ll inf=4e18;
int n,m;
vector<ii>adj[maxn+2];
ll dist[maxn+2][2];
int travel_plan(int N, int M, int r[][2], int l[], int K, int P[]){
n=N,m=M;
for(int q=0;q<m;q++){
adj[r[q][0]].push_back({r[q][1],l[q]});
adj[r[q][1]].push_back({r[q][0],l[q]});
}
for(int q=0;q<n;q++){
dist[q][0]=dist[q][1]=inf;
}
priority_queue<ii,vector<ii>,greater<ii> >pq;
for(int q=0;q<K;q++){
int x=P[q];
dist[x][0]=dist[x][1]=0;
pq.push({0,x});
}
while(pq.size()){
auto[jrk,idx]=pq.top();pq.pop();
if(dist[idx][1]<jrk)continue;
for(auto x : adj[idx]){
ll baru=x.sec+jrk;
if(dist[x.fir][0]>baru){
if(dist[x.fir][1]>dist[x.fir][0]){
pq.push({dist[x.fir][0],x.fir});
}
dist[x.fir][1]=dist[x.fir][0];
dist[x.fir][0]=baru;
}
else if(dist[x.fir][1]>baru){
dist[x.fir][1]=baru;
pq.push({dist[x.fir][1],x.fir});
}
}
}
return dist[0][1];
}
