#include "crocodile.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int maxn = 100005;
const int inf = 1e9 + 5;
int n, m, k;
vector<pair<int, int>> g[maxn];
struct vertex
{
int min1;
int min2;
int node;
friend bool operator < (const vertex& a, const vertex& b)
{
return a.min2 < b.min2 || (a.min2 == b.min2 && a.node < b.node);
}
};
set<vertex> s;
bool visited[maxn];
int dist[maxn];
int dist2[maxn];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
n = N;
m = M;
k = K;
for (int i = 0; i < m; ++i)
{
int x = R[i][0];
int y = R[i][1];
int w = L[i];
++x;
++y;
g[x].push_back(make_pair(y, w));
g[y].push_back(make_pair(x, w));
}
for (int i = 1; i <= n; ++i)
{
dist[i] = inf;
dist2[i] = inf;
}
for (int i = 0; i < k; ++i)
{
dist[P[i] + 1] = 0;
dist2[P[i] + 1] = 0;
}
for (int i = 1; i <= n; ++i)
{
s.insert({dist[i], dist2[i], i});
}
while (!s.empty())
{
auto [best, second_best, node] = (*s.begin());
s.erase(s.begin());
if (visited[node] == true)
{
continue;
}
visited[node] = true;
for (auto [next_node, w] : g[node])
{
if (visited[next_node] == false)
{
s.erase({dist[next_node], dist2[next_node], next_node});
int new_dist = second_best + w;
if (dist[next_node] > new_dist)
{
dist2[next_node] = dist[next_node];
dist[next_node] = new_dist;
}
else if (dist2[next_node] > new_dist)
{
dist2[next_node] = new_dist;
}
s.insert({dist[next_node], dist2[next_node], next_node});
}
}
}
return dist2[1];
}
