#include "crocodile.h"
#include <vector>
#include <queue>
#include <limits>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
struct Edge {
int to;
ll w;
};
struct Node {
ll val;
int id;
bool operator>(const Node &other) const {
return val > other.val;
}
};
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
vector<vector<Edge>> adj(N);
for (int i = 0; i < M; ++i) {
int u = R[i][0], v = R[i][1];
ll w = L[i];
adj[u].push_back({v, w});
adj[v].push_back({u, w});
}
vector<bool> exitChamber(N, false);
for (int i = 0; i < K; ++i)
exitChamber[P[i]] = true;
vector<ll> f(N, INF), best(N, INF), second(N, INF);
priority_queue<Node, vector<Node>, greater<Node>> pq;
for (int i = 0; i < N; ++i) {
if (exitChamber[i]) {
f[i] = 0;
pq.push({0, i});
}
}
while (!pq.empty()) {
Node cur = pq.top(); pq.pop();
int u = cur.id;
if (cur.val != f[u]) continue;
for (auto &edge : adj[u]) {
int v = edge.to;
if (exitChamber[v]) continue;
ll candidate = edge.w + f[u];
if (candidate < best[v]) {
second[v] = best[v];
best[v] = candidate;
} else if (candidate < second[v] && candidate != best[v]) {
second[v] = candidate;
}
if (second[v] < f[v]) {
f[v] = second[v];
pq.push({f[v], v});
}
}
}
return (int)f[1];
}
