#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define X first
#define Y second
const int MXN = 1e5+5;
const int inf = 1e9;
vector<pii> g[MXN];
int dis[MXN];
bool mark[MXN];
pii st[MXN];
priority_queue<pii> pq;
inline void upd(int v, int d) {
dis[v] = d;
for(auto [u, w] : g[v])
if(d+w<st[u].Y) {
st[u].Y = d+w;
if(st[u].Y<st[u].X) swap(st[u].X, st[u].Y);
pq.push({-st[u].Y, u});
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
for(int i=0; i<M; i++) {
g[R[i][0]].push_back({R[i][1], L[i]});
g[R[i][1]].push_back({R[i][0], L[i]});
}
fill(st, st+N, pii(inf, inf));
for(int i=0; i<N; i++) upd(i, inf);
for(int i=0; i<K; i++) upd(P[i], 0), mark[P[i]] = 1;
while(!pq.empty()) {
int d = -pq.top().X;
int v = pq.top().Y;
pq.pop();
if(mark[v]) continue;
upd(v, d);
mark[v] = 1;
}
return dis[0];
}
