#include "crocodile.h"
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
// Grafni qo'shnichilik ro'yxati ko'rinishida saqlash
vector<vector<pair<int, int>>> adj(N);
for (int i = 0; i < M; i++) {
adj[R[i][0]].push_back({R[i][1], L[i]});
adj[R[i][1]].push_back({R[i][0], L[i]});
}
// min1 - eng qisqa, min2 - ikkinchi eng qisqa masofa
vector<ll> min1(N, INF), min2(N, INF);
vector<bool> visited(N, false);
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
// Barcha chiqish xonalarini 0 masofa bilan boshlash
for (int i = 0; i < K; i++) {
min1[P[i]] = min2[P[i]] = 0;
pq.push({0, P[i]});
}
while (!pq.empty()) {
ll d = pq.top().first;
int u = pq.top().second;
pq.pop();
if (visited[u]) continue;
visited[u] = true;
// Agar 0-xonaga yetib kelgan bo'lsak, bu eng kichik T bo'ladi
if (u == 0) return (int)d;
for (auto& edge : adj[u]) {
int v = edge.first;
ll weight = edge.second;
ll new_dist = d + weight;
// v xonasi uchun eng yaxshi ikkita masofani yangilash
if (new_dist < min1[v]) {
min2[v] = min1[v];
min1[v] = new_dist;
} else if (new_dist < min2[v]) {
min2[v] = new_dist;
}
// Agar ikkinchi masofa yangilangan bo'lsa va hali tashrif buyurilmagan bo'lsa
if (min2[v] != INF && !visited[v]) {
pq.push({min2[v], v});
}
}
}
return (int)min2[0];
}
