| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 12 | 7 | 5 | 50.000% |
Однажды группа спелеологов отправилась покорять африканские пещеры. Углубившись достаточно далеко, они обнаружили что-то странное — пахло дымом. «Неужели мы подобрались к вулкану?» — удивленно спросил новичок. «Нет. Около вулкана пахнет серой», — ответил капитан. «Кто у нас занимался тушением костров?». Все неуверенно пожали плечами. «Итак, друзья, мы в ловушке».
Перед капитаном команды спелеологов возникла непосильная задача: как же вывести свою группу из пещеры, не сгорев? Пещера в терминах спелеологов состоит из множества «тоннелей» и «станций». Каждый тоннель соединяет какую-нибудь пару различных станций и имеет свою длину. У капитана имеется карта пещеры, и он знает, где они разводили костры, и где находится выход из пещеры.
Каждую секунду дым распространяется на 1 метр. Таким образом, тоннель длины k, смежный с уже задымленной станцией, заполнится дымом за k секунд, а также заполнится дымом и соответствующая станция. Если спелеологи находятся на станции, где есть дым, они задыхаются. Спелеологи бегут со скоростью 1 метр в секунду. Изначально дым есть только в тех станциях, где спелеологи разводили костры.
Перемещаться по тоннелям можно в обе стороны. Если спелеологи прибывают на станцию одновременно с дымом, то они задыхаются (это верно и для той станции, где расположен выход). Гарантируется, что сейчас спелеологи находятся на станции, где нет дыма.
В первой строке входных данных содержится три целых числа N, M и K — количество станций, тоннелей и станций с кострами соответственно (2 ≤ N ≤ 2 · 105, 0 ≤ M ≤ 2 · 105, 1 ≤ K < N).
Во второй строке содержится K различных чисел ai — номера станций, в которых спелеологи разводили костры (1 ≤ ai ≤ N).
Следующие M строк описывают тоннели. Каждое описание состоит из трех чисел xi, yi и li, обозначающих номера станций, которые соединяет i-ый тоннель, и его длину в метрах (1 ≤ xi, yi ≤ N, 1 ≤ li ≤ 109, xi ≠ yi).
В последней строке входных данных содержится 2 числа S и F — номер станции, на которой сейчас находятся спелеологи и номер станции, в которой находится выход из пещеры (1 ≤ S, F ≤ N).
Выведите единственное число — минимальное количество секунд, которое требуется спелеологам для того, чтобы выбраться из пещеры, либо «-1», если спелеологам не удастся выбраться.
6 5 1 6 1 2 20 2 3 2 3 4 1 2 5 1 5 6 3 4 1
23
6 6 2 4 1 4 1 1 6 5 1 2 4 1 1 5 2 5 6 2 5 1 2 3 6
-1