#include <bits/stdc++.h>
#include "crocodile.h"
using namespace std;
long long inf = 1e16;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[])
{
int n = N;
vector<vector<pair<int, long long>>> graph(N);
vector<int> vis(n);
vector<pair<long long, long long>> dis(n, {inf, inf});
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]) {
long long comp = adj.second;
if (comp < dis[adj.first].first) {
long long im = comp;
comp = dis[adj.first].first;
dis[adj.first].first = im;
}
if (comp < dis[adj.first].second) {
dis[adj.first].second = comp;
pq.push({-dis[adj.first].second, adj.first});
}
}
}
}
while (pq.size() > 0) {
auto t = pq.top();
pq.pop();
if (vis[t.second]) {
continue;
}
vis[t.second] = 1;
if (t.second == 0) {
return dis[0].second;
}
long long d = -t.first;
for (auto adj : graph[t.second]) {
if (!vis[adj.first]) {
long long comp = adj.second + d;
if (comp < dis[adj.first].first) {
long long im = comp;
comp = dis[adj.first].first;
dis[adj.first].first = im;
}
if (comp < dis[adj.first].second) {
dis[adj.first].second = comp;
pq.push({-dis[adj.first].second, adj.first});
}
}
}
}
return dis[0].second;
}
