#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
vector<pair<int, int>> graph[N];
int n, m;
int dijkstra(int exits[], int sz)
{
const int INF = 1e9;
vector<int> dist(n, INF);
vector<int> vis(n, 0);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
for (int i = 0; i < sz; i++)
{
dist[exits[i]] = 0;
vis[exits[i]] = 1;
q.push({0, exits[i]});
}
while (q.size())
{
int d = q.top().first;
int u = q.top().second;
vis[u]++;
q.pop();
if (d > dist[u])
continue;
if (vis[u] == 1) // remove first choice, can't take that shit
{
for (auto i : graph[u])
{
int w = i.first;
int v = i.second;
if (dist[v] > dist[u] + w)
{
dist[v] = dist[u] + w;
q.push({dist[v], v});
}
}
continue;
}
for (auto i : graph[u])
{
int w = i.first;
int v = i.second;
if (dist[v] > dist[u] + w)
{
dist[v] = dist[u] + w;
if (v == 0)
{
return dist[v];
}
q.push({dist[v], v});
}
}
}
int ans = dist[0];
return ans;
}
int travel_plan(int Nn, int Mm, int R[][2], int L[], int K, int P[])
{
n = Nn, m = Mm;
for (int i = 0; i < m; i++)
{
graph[R[i][0]].push_back({L[i], R[i][1]});
graph[R[i][1]].push_back({L[i], R[i][0]});
}
return dijkstra(P, K);
}
