#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pr = pair<int, int>;
#define pb push_back
const int INF = 1e9+7;
int n, m;
struct Node{
int next, v, id;
};
vector<vector<Node>> edge;
vector<bool> fin, ban, vis;
vector<int> dp(n, INF);
int dijkstra() {
vector<vector<int>> dist(n, vector<int>(2, INF)); // min, and second min to a finish
vector<bool> vis;
vector<pr> prev(n, {-1, -1});
priority_queue<pr, vector<pr>, greater<pr>> pq; // val, node
for (int i = 0; i < n; i++) {
if (fin[i]) {
pq.push({0, i});
dist[i][1] = 0;
}
}
while (!pq.empty()) {
auto [d, node] = pq.top(); pq.pop();
if (dist[node][1] < d) continue;
for (auto [next, v, id] : edge[node]) {
if (dist[next][0] > d + v) {
dist[next][1] = dist[next][0];
dist[next][0] = d + v;
pq.push({dist[next][1], next});
}
else if (dist[next][1] > d + v) {
dist[next][1] = d + v;
pq.push({d + v, next});
}
}
}
return dist[0][1];
}
// int dfs(int node, int prev) {
// if (vis[node]) return dp[node];
// vis[node] = 1;
// if (fin[node]) return dp[node] = 0;
// // vector<Node> banned, allow;
// int a = INF, b = INF;
// for (auto [next, v, id] : edge[node]) {
// if (next == prev) continue;
// int t = dfs(next, node) + v;
// if (t < a) {
// b = a;
// a = t;
// }
// else if (t < b) {
// b = t;
// }
// }
// return dp[node] = b;
// }
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
n = N; m = M;
edge.assign(n, {});
ban.assign(m, 0);
vis.assign(n, 0);
fin.assign(n, 0);
for (int i = 0; i < m; i++) {
edge[R[i][0]].pb({R[i][1], L[i], i});
edge[R[i][1]].pb({R[i][0], L[i], i});
}
for (int i = 0; i < K; i++) fin[P[i]] = 1;
int res = dijkstra();
if (res == INF) return -1;
else return res;
return N;
}
