#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
int n = M;
vector<vector<pair<int, long long>>> graph(N);
vector<int> vis(n);
vector<multiset<long long>> dis(n);
for (int i = 0; i < M; i++) {
graph[R[i][0]].push_back({R[i][1], L[i]});
graph[R[i][1]].push_back({R[i][0], L[i]});
}
priority_queue<pair<long long, int>> pq;
for (int i = 0; i < K; i++) {
vis[P[i]] = 1;
for (auto adj : graph[P[i]]) {
if (!vis[adj.first]) {
dis[adj.first].insert(adj.second);
if (dis[adj.first].size() > 1) {
auto it = dis[adj.first].begin();
it++;
pq.push({-*it, adj.first});
}
}
}
}
while (pq.size() > 0) {
auto t = pq.top();
pq.pop();
if (vis[t.second]) {
continue;
}
long long d = -t.first;
for (auto adj : graph[t.second]) {
if (!vis[adj.first]) {
dis[adj.first].insert(d + adj.second);
if (dis[adj.first].size() > 1) {
auto it = dis[adj.first].begin();
it++;
pq.push({-*it, adj.first});
}
}
}
}
auto it = dis[0].begin();
it++;
return *it;
}
