Непредусмотрительные спелеологи
시간 제한1초메모리 제한1024 MB
가중 그래프에서 불이 매초 1미터씩 번질 때, 스펠레올로지스트가 S에서 F까지 불보다 먼저 도착하는 최단 시간을 구한다.
문제
Однажды группа спелеологов отправилась покорять африканские пещеры. Углубившись достаточно далеко, они обнаружили что-то странное — пахло дымом. «Неужели мы подобрались к вулкану?» — удивленно спросил новичок. «Нет. Около вулкана пахнет серой», — ответил капитан. «Кто у нас занимался тушением костров?». Все неуверенно пожали плечами. «Итак, друзья, мы в ловушке».
Перед капитаном команды спелеологов возникла непосильная задача: как же вывести свою группу из пещеры, не сгорев? Пещера в терминах спелеологов состоит из множества «тоннелей» и «станций». Каждый тоннель соединяет какую-нибудь пару различных станций и имеет свою длину. У капитана имеется карта пещеры, и он знает, где они разводили костры, и где находится выход из пещеры.
Каждую секунду дым распространяется на 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», если спелеологам не удастся выбраться.