// https://oj.uz/problem/view/IOI11_crocodile
/** Needed for linking!!! */
#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF (ll)1e18
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
vector<map<int, int>> graph(N);
vector<set<int>> visited(N);
for (int i = 0; i < M; i++) {
int u = R[i][0];
int v = R[i][1];
graph[u][v] = graph[v][u] = L[i];
}
// Run Dijkstra's and only care about the second best distance, propagated downwards
vector<vector<ll>> dist(graph.size(), {INF, INF});
priority_queue<pair<ll, ll>> pq;
for (int i = 0; i < K; i++) {
pq.push({0, P[i]});
dist[P[i]][0] = dist[P[i]][1] = 0;
}
while (pq.size()) {
auto [d, u] = pq.top();
pq.pop();
d = -d;
if (d > dist[u][1]) {
continue;
}
// Thank you to Sreepranad Devarakonda from USACO Guide
for (auto& [v, w] : graph[u]) {
ll cost = w + d;
// ! We only add to the priority queue (for a downstream effect) when we set the 2nd shortest distance
if (cost < dist[v][0]) {
// The first shortest distance can become the 2nd shortest distance
if (dist[v][0] != dist[v][1] && dist[v][0] < INF) {
dist[v][1] = dist[v][0];
pq.push({-dist[v][1], v});
}
dist[v][0] = cost;
}
else if (cost < dist[v][1]) {
dist[v][1] = cost;
pq.push({-cost, v});
}
}
}
return dist[0][1];
}
