#include "crocodile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < M; i++) {
adj[R[i][0]].emplace_back(R[i][1], L[i]);
adj[R[i][1]].emplace_back(R[i][0], L[i]);
}
ll bign = 1e18;
vector<pair<ll, ll>> stat(N, {bign, bign});
// value, curin
priority_queue<pair<ll, int>> pqai3;
for (int i = 0; i < K; i++) {
stat[P[i]] = {0, 0};
for (auto a : adj[P[i]]) {
pqai3.emplace(-a.second, a.first);
}
}
while (!pqai3.empty()) {
pair<ll, int> pii = pqai3.top();
pqai3.pop();
if (-pii.first >= stat[pii.second].second) continue;
if (-pii.first >= stat[pii.second].first)
stat[pii.second].second = -pii.first;
else {
stat[pii.second].second = stat[pii.second].first;
stat[pii.second].first = -pii.first;
}
for (auto a : adj[pii.second])
pqai3.emplace(-(stat[pii.second].second + a.second), a.first);
}
// for (int i = 0; i < N; i++) {
// cout << stat[i].first << " " << stat[i].second << "\n";
// }
return stat[0].second;
}
