#include "crocodile.h"
#include<bits/stdc++.h>
#define pb push_back
#define lint long long int
using namespace std;
int _n, _m, _k;
vector<bool> is_exit;
vector<vector<pair<int, int>>> edge;
int travel_plan (int n, int m, int r[][2], int l[], int k, int p[]) {
_n=n; _m=m; _k=k;
edge.resize(n);
for (int i = 0; i < m; i ++) {
edge[r[i][0]].pb({r[i][1], l[i]});
edge[r[i][1]].pb({r[i][0], l[i]});
}
is_exit.resize(n, false);
for (int i = 0; i < k; i ++) {
is_exit[p[i]] = true;
}
vector<int> visited(n, 0);
vector<pair<int, int>> dis(n, {1e9, 1e9});
priority_queue<pair<int, pair<int, int>>> q;
// for (int i = 0; i < k ; i ++) {
// for (auto [v, w] : edge[p[i]]) {
// q.push({-w, {v, p[i]}});
// }
// }
int MN_V = 1E9, MN_W = 1E9;
for (auto [v, w] : edge[0]) {
if (w < MN_W) {
if (MN_V != 1E9) q.push({-MN_W, {MN_V, 0}});
MN_W = w; MN_V = v;
}
else {
q.push({-w, {v, 0}});
}
}
while (!q.empty()) {
int w = -q.top().first;
int v = q.top().second.first, par = q.top().second.second;
q.pop();
// cout << w << " " << v << " " << par << endl;
if (visited[v] > 2) {continue;}
visited[v] ++;
if (is_exit[v]) {
// cout << "EXXXIIIITTTTT: " << v << " " << w << " " << par << endl;
return w;
// break;
}
if (w < dis[v].first) {
dis[v].second = dis[v].first;
dis[v].first = w;
}
else if (w < dis[v].second) {
dis[v].second = w;
}
int mn_v = 1e9, mn_w = 1e9, par_mn_v = 1e9;
for (auto [new_v, new_w] : edge[v]) {
// cout << " :: " << new_v << " " << new_w << endl;
if (new_v == par) continue;
// if (visited[new_v] < 2) {
if (new_w+w < mn_w) {
// cout << ":1 -- " << new_w << " " << w << " " << mn_w << endl;
if (mn_v != 1e9) {q.push({-mn_w, {mn_v, par_mn_v}});}
mn_v = new_v; mn_w = new_w + w; par_mn_v = v;
// cout << "mn_v: " << mn_v << " mn_w: " << mn_w << " par_mn_v: " << par_mn_v << endl;
}
else {
// cout << ":2" << endl;
q.push({-(new_w+w), {new_v, v}});
}
// }
}
}
// for (int i = 0; i < n; i ++) {
// cout << "i=" << i << ": " << dis[i].first << " " << dis[i].second << endl;
// }
// vector<bool> visited(n, false);
// vector<pair<int, int>> dis(n, {1e9, 1e9});
// priority_queue<pair<int, int>> q;
// q.push({0, 0});
// visited[0] = true;
// while(!q.empty()) {
// int w = -q.top().first, v = q.top().second;
// q.pop();
// int mn_v=1e9, mn_w=1e9, next_is_exit = false;
// // if this node has one or more exit => block the smallest exit, push others
// // if this node has no exit => block the smallest one
// int exit_cnt = 0;
// pair<int, int> min1_exit = {1e9, 1e9}, min2_exit = {1e9, 1e9};
// for (auto [new_v, new_w] : edge[v]) {
// if (visited[new_v]) continue;
// if (is_exit[new_v]) {
// exit_cnt ++;
// if (exit_cnt == 1) {
// // found the first exit, the nodes that is blocked previously can be push.
// if (mn_v != 1e9) q.push({-mn_w, mn_v});
// }
// if (new_w + w < min1_exit.second) {
// min2_exit = min1_exit;
// min1_exit = {new_v, new_w + w};
// }
// else if (new_w + w < min2_exit.second) {
// min2_exit = {new_v, new_w + w};
// }
// }
// else {
// if (exit_cnt == 0) {
// // no exit found until now
// // need to check if this node has smaller w
// if (new_w + w < mn_w) {
// if (mn_v != 1e9) q.push({-mn_w, mn_v});
// mn_w = new_w + w;
// mn_v = new_v;
// }
// else {
// q.push({-(new_w+w), new_v});
// }
// }
// else if (exit_cnt == 1) {
// q.push({-(new_w+w), new_v});
// }
// // else if exit_cnt > 1, no need to push, already found a shortest path
// }
// }
// if (exit_cnt > 1) {
// dis[v] = min2_exit.second;
// }
// }
// for (int i = 0; i < n; i ++) {
// if (is_exit[i]) {
// cout << "*";
// }
// cout << "i=" << i << ": ";
// cout << dis[i].first << " " << dis[i].second << endl;
// }
return 0;
}
