#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e15; // Không nên để 1e18 để tránh tràn số khi + w
struct Edge {
int v, w;
};
struct Node {
int u;
ll d;
bool operator>(const Node& o) const {
return d > o.d;
}
};
// Sử dụng mảng tĩnh để an toàn hơn về bộ nhớ
vector<Edge> adj[100005];
ll d1[100005], d2[100005];
int travel_plan(int N, int M, int R[][2], int L[], int K, int P[]) {
// 1. Reset dữ liệu triệt để
for (int i = 0; i < N; i++) {
vector<Edge>().swap(adj[i]); // Giải phóng bộ nhớ vector
d1[i] = d2[i] = INF;
}
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]});
}
priority_queue<Node, vector<Node>, greater<Node>> pq;
// 2. Lối thoát
for (int i = 0; i < K; i++) {
int u = P[i];
d1[u] = d2[u] = 0;
pq.push({u, 0});
}
// 3. Dijkstra
while (!pq.empty()) {
int u = pq.top().u;
ll d = pq.top().d;
pq.pop();
if (d > d2[u]) continue;
for (auto& e : adj[u]) {
ll tmp = d + e.w;
if (tmp < d1[e.v]) {
d2[e.v] = d1[e.v];
d1[e.v] = tmp;
// Chỉ đẩy vào khi d2 thực sự được cập nhật giá trị hữu hạn
if (d2[e.v] < INF) pq.push({e.v, d2[e.v]});
} else if (tmp < d2[e.v]) {
d2[e.v] = tmp;
pq.push({e.v, d2[e.v]});
}
}
}
return (int)d2[0];
}
