Tình trạng AC: Đã có người AC. RussVN123 là người đầu tiên AC 🎉.

Bài gốc: nodeblockeddijkstra

Trong một vũ trụ song song, nơi mà TikTok không chỉ là một ứng dụng mà là một chiều không gian, Nhi - một blogger chính gốc với 1 triệu follower trên X, đang đối mặt với drama lớn nhất trong đời. Chuyện bắt đầu từ một buổi chiều thứ Bảy, khi Nhi livestream tại quán trà sữa "Trăng Rằm" - địa điểm trending nhất khu phố, nơi mà các influencer thi nhau check-in với ly trà sữa topping trân châu kim cương phát sáng. Nhưng, ôi không, một sự kiện kinh hoàng đã xảy ra: ly trà sữa của Nhi bị đánh giá 1* trên group "Team Qua Đường" vì "trân châu dai như dây chun" và "đường hóa học như lời hứa của crush". Drama bùng nổ, kéo theo một lời nguyền "ác quỷ" từ một tài khoản ẩn danh tự xưng là "Chúa Tể Quán Tạp Hóa".

Lời nguyền tuyên bố: "Ai không giải được bí ẩn của quán Trăng Rằm trong vòng 24 giờ sẽ bị biến thành một quả chuối và bị team qua đường chụp ảnh đăng story với caption 'Chất lượng 1*'!" Nhi, cùng với ba người bạn thân: Duyên (chuyên gia phân tích meme), Tín (pro-player game Free Fire với rank Top 1 server), và Khôi (một coder tự học từng hack được WiFi hàng xóm), quyết định bước vào cuộc phiêu lưu để hóa giải lời nguyền. Họ phát hiện ra rằng bí ẩn nằm ở một bản đồ bí mật của khu phố, nơi các quán trà sữa, tiệm tạp hóa, và nhà của các influencer được kết nối như một đồ thị có hướng. Nhưng, bản đồ này không đơn giản - nó được mã hóa bởi chính "Chúa Tể Quán Tạp Hóa", kẻ đã sử dụng 15 tầng thuật toán từ thời Hy Lạp cổ đại đến blockchain hiện đại để làm rối não người giải.

Khu phố của Nhi có ~N~ địa điểm, được đánh số từ ~1~ đến ~N~, và ~M~ con đường một chiều nối các địa điểm. Mỗi con đường từ địa điểm ~u~ đến địa điểm ~v~ có một "độ toxic" ~w~ (số nguyên không âm), biểu thị mức độ drama mà team qua đường có thể gây ra nếu Nhi đi qua con đường đó. Độ toxic này được tính dựa trên số lượng bài review 1* mà các tiệm tạp hóa trên đường nhận được, nhân với số lần hashtag #TeamQuaĐường xuất hiện trên X trong vòng 24 giờ gần nhất.

Nhi cần tìm đường đi từ nhà mình (địa điểm ~1~) đến quán Trăng Rằm (địa điểm ~N~), sao cho tổng độ toxic của các con đường đi qua là nhỏ nhất có thể. Nhưng, có một plot twist: một số địa điểm là tiệm tạp hóa bị review 1*, và Nhi phải tránh tuyệt đối các địa điểm này, vì nếu đi qua, cô sẽ bị team qua đường chụp ảnh và đăng lên story với caption "Đi nhầm đường rồi chị ơi!". Các tiệm tạp hóa này được đánh dấu trong danh sách ~K~ địa điểm cấm, với mỗi địa điểm cấm có chỉ số ~c[i]~.

Để làm mọi chuyện thêm rối, Chúa Tể Quán Tạp Hóa đã thêm một lớp bảo mật: bản đồ được mã hóa dưới dạng một chuỗi nhị phân dài ~10^{18}~ bit, nhưng may mắn thay, Tín đã dùng kỹ năng chơi Free Fire của mình để giải mã và phát hiện ra rằng chuỗi này thực chất chỉ là một biểu diễn giả của đồ thị, và số bit thực sự cần xử lý chỉ khoảng... ~1000~ bit. Duyên thì phát hiện ra rằng các con đường trong đồ thị có một đặc điểm kỳ lạ: nếu bạn đi qua một con đường có độ toxic chia hết cho ~7~ (con số yêu thích của Chúa Tể), bạn sẽ bị trừ ~1~ điểm vibe, và nếu vibe về ~0~, bạn sẽ bị biến thành quả chuối ngay lập tức! Và Duyên cũng phát hiện ra nếu tổng toxic là số nguyên tố, Nhi sẽ được tặng voucher trà sữa miễn phí.

Khôi đã bị ác quỷ bịt miệng vì đã biết quá nhiều, trước đó anh ấy đã kịp la lên "dijkstra", và cho đến giờ vẫn chưa có bất kì thông tin gì từ anh ấy.

Nhiệm vụ của bạn:

Hãy giúp Nhi và team tìm đường đi từ địa điểm 1 đến địa điểm N, sao cho tổng độ toxic là nhỏ nhất, đồng thời tránh tất cả các địa điểm cấm. Nếu không tồn tại đường đi nào thỏa mãn, hãy trả về ~-1~ để Nhi biết mà tìm cách xin lỗi team qua đường trên livestream. Đừng lo về chu trình âm, vì Khôi đã kiểm tra và xác nhận đồ thị không có chu trình âm.

Input:

• Dòng đầu tiên chứa ba số nguyên ~N~, ~M~, ~K~ (không biết chính xác giới hạn, chỉ biết là ~N ≤ 10^{18}, M ≤ 10^{18}, 0 ≤ K ≤ N~), lần lượt là số địa điểm, số con đường, và số địa điểm cấm.
• ~M~ dòng tiếp theo, mỗi dòng chứa ba số nguyên ~u~, ~v~, ~w~ (cũng không biết chính xác nốt, chỉ biết là ~u~ và ~v~ ~≤ N~, ~w ≤ 10^{18}~), biểu thị một con đường một chiều từ ~u~ đến ~v~ với độ toxic ~w~.
• Dòng cuối chứa ~K~ số nguyên ~c[1], c[2], ..., c[K~ (~1 ≤ c[i] ≤ N, c[i]~ đôi một khác nhau), là các địa điểm cấm.

Output:

• Một số nguyên duy nhất là tổng độ toxic nhỏ nhất của đường đi từ ~1~ đến ~N~ mà không đi qua các địa điểm cấm. Nếu không tồn tại đường đi, in ~-1~.

Input:

4 5 1
1 2 10
2 3 20
1 3 100
3 4 30
2 4 50
3

Output::

60

Giải thích:

• Có 4 địa điểm, 5 con đường, 1 địa điểm cấm (địa điểm 3).
• Đường đi khả thi: 1 -> 2 -> 4, với độ toxic là 10 + 50 = 60.
• Không thể đi qua địa điểm 3, nên các đường liên quan đến 3 bị bỏ qua.
• Đây là trường hợp đơn giản nhất, nhưng đừng để bị lừa, vì các test case thật có thể dài như một bài diss track của rapper top 1 X!

Giới hạn:

• 100% test có ~1 ≤ N ≤ 1000~, ~0 ≤ M ≤ 10^6~, ~0 ≤ K ≤ N, 1 ≤ u~, ~v ≤ N, 0 ≤ w ≤ 10^9~, ~c[K 1 ≤ c[i] ≤ N, c[i]~.

Lưu ý cuối cùng từ Chúa Tể Quán Tạp Hóa

Nếu bạn không AC được bài này, bạn sẽ bị biến thành một quả chuối và bị đăng lên story của team qua đường với caption "Chất lượng code 1*!". Nhưng nếu bạn là người ac bài này đầu tiên, nmk sẽ thay Nhi thực hiện lời hứa sẽ tặng một ly trà sữa miễn phí cho ai đầu tiên giải được, kèm theo đó là một badge custom (liên hệ nomoka.nmk@proton.me) cực xịn sò con bò.

Chúc bạn may mắn, và đừng để bị team qua đường chụp ảnh!