#include "crocodile.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 1<<17;
vector<array<int, 2>> g[maxn];
array<int, 2> dist[maxn];
priority_queue<array<int, 2>> pq;
void relax(int u, int d) {
if(d > 1<<30) return;
int old = dist[u][1];
if(dist[u][0] > d) {
dist[u][1] = dist[u][0];
dist[u][0] = d;
} else if(dist[u][1] > d) {
dist[u][1] = d;
}
if(dist[u][1] < old)
pq.push({-dist[u][1], u});
}
int travel_plan(int n, int m, int r[][2], int l[], int k, int p[]) {
fill(begin(dist), end(dist), array<int, 2>{1<<30, 1<<30});
for(int i = 0; i < k; i++) {
relax(p[i], 0);
relax(p[i], 0);
}
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]});
}
while(!pq.empty()) {
auto [cst, u] = pq.top();
pq.pop();
cst *= -1;
if(cst > dist[u][1]) continue;
for(auto [i, w] : g[u])
relax(i, cst + w);
}
return dist[0][1];
}
