#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
const int MAXN = 100000;
const int INF = 2e9 + 1;
vector<int> adj[MAXN];
vector<int> cost[MAXN];
long long dp[MAXN], dp2[MAXN];
struct node {
int nod;
long long rez;
};
priority_queue<node> pq;
node top;
bool operator <(node a, node b) {
return a.rez > b.rez;
}
int travel_plan(int n, int m, int R[][2], int L[], int k, int P[]) {
//fac un dijkstra si incep sa pun muchiile de la nodurile de iesire
//si stiu timpul minim sa ies dintr-un nod ca fiind al doiea minim dintre vecinii pe care ii stiu pana acum
//deci fac un dijkstra si prima apritie a unui nod o ignor ca imi trebuie doar a doua ca imi trebuie al doilea minim de la fiecare
int i, x, y, nod, nr, s;
for (i = 0; i < m; i++) {
x = R[i][0];
y = R[i][1];
adj[x].push_back(y);
adj[y].push_back(x);
cost[x].push_back(L[i]);
cost[y].push_back(L[i]);
}
for (i = 0; i < n; i++) {
dp[i] = dp2[i] = INF;
}
for (i = 0; i < k; i++) {
x = P[i];
dp[x] = dp2[x] = 0;
pq.push({x, 0});
}
while (!pq.empty()) {
top = pq.top();
pq.pop();
nod = top.nod;
if (top.rez == dp2[nod]) {//al doilea minim
nr = adj[nod].size();
for (i = 0; i < nr; i++) {
x = adj[nod][i];
s = dp2[nod] + cost[nod][i];
if (s < dp[x]) {
dp2[x] = dp[x];
dp[x] = s;
pq.push({x, dp[x]});
} else if (s < dp2[x]) {
dp2[x] = s;
pq.push({x, dp2[x]});
}
}
}
}
return dp2[0];
}
