#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx = 1e5 + 5;
const ll INF = 1e18;
ll min1[nx], min2[nx];
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
vector<pair<int,ll>> adj[nx];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
fill(min1, min1 + nx, INF);
fill(min2, min2 + nx, INF);
for (int i = 0; i < N; i++) adj[i].clear();
for (int i = 0; i < M; i++) {
int u = R[i][0], v = R[i][1], w = L[i];
adj[u].emplace_back(v, w);
adj[v].emplace_back(u, w);
}
for (int i = 0; i < K; i++) {
int u = P[i];
min1[u] = 0, min2[u] = 0;
pq.emplace(0, u);
}
while (!pq.empty()) {
auto [w, u] = pq.top();
pq.pop();
if (min2[u] < w) continue;
for (auto [v, ww] : adj[u]) {
ll new_w = w + ww;
if (new_w < min1[v]) {
min2[v] = min1[v];
min1[v] = new_w;
if (min2[v] != INF) pq.emplace(min2[v], v);
} else if (new_w < min2[v]) {
min2[v] = new_w;
pq.emplace(min2[v], v);
}
}
}
return min2[0];
}
