#include "crocodile.h"
#include <vector>
#include <queue>
struct Edge
{
Edge(int v, long long w) : dest(v), weight(w) {}
int dest;
long long weight;
bool operator <(const Edge &other) const
{
return (other.weight < weight);
}
};
const int MAXN = 1e5;
const long long INFTY = 1e18;
std::vector<Edge> graph[MAXN];
std::priority_queue<Edge> paths;
long long shortest[MAXN][2];
void dijkstra()
{
while (!paths.empty())
{
int node = paths.top().dest;
long long dist = paths.top().weight;
paths.pop();
if (shortest[node][0] == INFTY)
shortest[node][0] = dist;
else if (shortest[node][1] == INFTY)
{
shortest[node][1] = dist;
for (Edge &edge : graph[node])
paths.emplace(edge.dest, dist + edge.weight);
}
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
std::fill_n((long long *)shortest, N * 2, INFTY);
for (int iEdge = 0; iEdge < M; iEdge++)
{
graph[R[iEdge][0]].emplace_back(R[iEdge][1], L[iEdge]);
graph[R[iEdge][1]].emplace_back(R[iEdge][0], L[iEdge]);
}
for (int iExit = 0; iExit < K; iExit++)
{
shortest[P[iExit]][0] = 0;
paths.emplace(P[iExit], 0);
}
dijkstra();
return shortest[0][1];
}
