#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = a; i <= b; ++i)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define pii pair<int,int>
const int MAXN = 1e5 + 10;
const int INF = 1e9 + 5;
vector<pii> g[MAXN];
int dist[MAXN][2];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
rep(i,0,M-1) {
int u = R[i][0], v= R[i][1], w= L[i];
g[u].pb({v,w});
g[v].pb({u,w});
}
priority_queue<pii,vector<pii>,greater<pii>> pq;
rep(i,0,N) dist[i][0] = dist[i][1] = INF;
rep(i,0,K-1) {
pq.push({0,P[i]});
dist[P[i]][0] = dist[P[i]][1] = 0;
}
while (!pq.empty()) {
pii tp = pq.top();
int cw = tp.first,u = tp.second;
pq.pop();
if(dist[u][1] < cw) continue;
for (const auto &e : g[u]) {
int v = e.first, w = e.second;
if (dist[v][0] > cw + w) {
if(dist[v][0] < dist[v][1]) pq.push({dist[v][0],v});
dist[v][1] = dist[v][0];
dist[v][0] = cw+w;
} else if(dist[v][1] > cw+w) {
pq.push({cw+w,v});
dist[v][1] = cw+w;
}
}
}
return dist[0][1];
}
