#include <bits/stdc++.h>
#include "crocodile.h"
#define all(v) begin(v), end(v)
#define ii pair<int, int>
#define siz(v) (int)(v).size()
#define lli pair<long long, int >
#define exit __exit
#define fi first
#define se second
using namespace std;
const int MAXN = 1e5 + 5, MAXM = 1e6 + 6;
const long long inf = 1e18 + 132;
template<class X, class Y> bool minimize(X &x, const Y &y){return x > y ? x = y, 1: 0;}
int numNode, numEdge, numExit, exit[MAXN];
long long dist[MAXN][2];
vector<ii > adj[MAXN];
void dijsktra(){
priority_queue<lli, vector<lli >, greater<lli > > q;
memset(dist, 0x3f, sizeof dist);
for(int i = 1; i <= numExit; i++){
int u = exit[i];
q.emplace(dist[u][0] = dist[u][1] = 0, u);
}
while(siz(q)){
int u = q.top().se;
long long len = q.top().fi;
q.pop();
if (len > dist[u][1]) continue;
for(ii x: adj[u]){
int v = x.fi, w = x.se;
if (dist[v][0] > dist[u][1] + w){
dist[v][1] = dist[v][0];
dist[v][0] = dist[u][1] + w;
if (dist[v][1] < inf) q.emplace(dist[v][1], v);
}else if (minimize(dist[v][1], dist[u][1] + w)) {
if (dist[v][1] < inf) q.emplace(dist[v][1], v);
}
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
numNode = N, numEdge = M, numExit = K;
for(int i = 1; i <= numEdge; i++){
int u = R[i - 1][0], v = R[i - 1][1], w = L[i - 1];
u++; v++;
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
for(int i = 1; i <= numExit; i++){
exit[i] = P[i - 1];
exit[i]++;
}
dijsktra();
return dist[1][1];
}
