#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;
int dijkstra() {
vector<vector<int>> dist(n, vector<int>(2, INF)); // min, and second min to a finish
vector<bool> vis(n, 0);
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][0] = 0;
dist[i][1] = 0;
}
}
while (!pq.empty()) {
auto [d, node] = pq.top(); pq.pop();
if (vis[node]) continue;
vis[node] = 1;
for (auto [next, v, id] : edge[node]) {
if (dist[next][0] > d + v) {
dist[next][1] = dist[next][0];
dist[next][0] = d + v;
if (dist[next][1] != INF)
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 travel_plan(int N, int M, int R[][2], int L[], int K, int P[]){
n = N; m = M;
edge.assign(n, {});
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;
}
