#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
#define t_road pair<int, num>
#define t_roads vector<t_road>
#define graph vector<t_roads>
#define num long long
#define next first
#define cost second
#define ndata vector<num>
#define inf 1e18
#define ni pair<num, int>
#define pq set<ni>
graph roads;
ndata t_max;
ndata t_mix;
pq update_queue;
bool _update (int index, num value) {
if (t_max[index] >= value) {
t_mix[index] = t_max[index];
t_max[index] = value;
} else if (t_mix[index] > value) {
t_mix[index] = value;
} else return false;
return t_mix[index] != inf;
}
void update (int index, num value) {
ni data = { t_mix[index], index };
if (_update(index, value)) {
if (update_queue.find(data) != update_queue.end())
update_queue.erase(data);
update_queue.insert({ t_mix[index], index });
}
}
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
roads.resize(N);
t_max.resize(N, inf);
t_mix.resize(N, inf);
for (int iR = 0; iR < M; iR ++) {
int a = R[iR][0];
int b = R[iR][1];
int c = L[iR];
roads[a].push_back({ b, c });
roads[b].push_back({ a, c });
}
for (int i = 0; i < K; i ++) {
update(P[i], 0);
update(P[i], 0);
}
while (update_queue.size() != 0) {
ni position = *update_queue.begin();
update_queue.erase(position);
int current = position.second;
num time = position.first;
if (current == 0) return time;
for (t_road next_road : roads[current]) {
num next_time = next_road.cost + time;
int next_node = next_road.next;
update(next_node, next_time);
}
}
return N;
}
