#include "crocodile.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>
typedef long long llong;
const int MAXN = 100000 + 10;
const int INF = 2e9;
struct Node
{
int min;
int min2;
int node;
friend bool operator < (const Node &a, const Node &b)
{
return a.min2 < b.min2 || (a.min2 == b.min2 && a.node < b.node);
}
};
int n, m;
int min[MAXN];
int min2[MAXN];
int dist[MAXN];
bool vis[MAXN];
std::set <Node> s;
std::vector <std::pair <int,int>> g[MAXN];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
n = N; m = M;
for (int i = 0 ; i < m ; ++i)
{
g[R[i][0] + 1].push_back({R[i][1] + 1, L[i]});
g[R[i][1] + 1].push_back({R[i][0] + 1, L[i]});
}
std::fill(min + 1, min + 1 + n, INF);
std::fill(min2 + 1, min2 + 1 + n, INF);
for (int i = 0 ; i < K ; ++i)
{
min[P[i] + 1] = min2[P[i] + 1] = 0;
}
for (int i = 1 ; i <= n ; ++i)
{
s.insert({min[i], min2[i], i});
}
while (!s.empty())
{
auto [currMIN, currDist, node] = (*s.begin());
s.erase(s.begin());
if (vis[node])
{
continue;
}
vis[node] = true;
for (const auto &[u, dist] : g[node])
{
if (vis[u])
{
continue;
}
s.erase(s.find({min[u], min2[u], u}));
if (min[u] > currDist + dist)
{
min2[u] = min[u];
min[u] = currDist + dist;
} else if (min2[u] > currDist + dist)
{
min2[u] = currDist + dist;
}
s.insert({min[u], min2[u], u});
}
}
return min2[1];
}
