D. Путь исследования
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Участники Bubble Cup X собрались после соревнования и обсуждают, как лучше всего узнать страну-организатор и города в ней.

После небольшого исследования карты Сербии участники выяснили следующий факт: в стране есть V городов, которые пронумерованы от 1 до V, и E двусторонних дорог, соединяющих города. У каждой дороги есть вес (время, необходимое для прохода по этой дороге).

На Bubble Cup есть N команд, поэтому участники придумали следующий план: каждая из N команд начнет свой путь в одном из V городов, возможно, некоторые команды будут иметь одинаковую начальную позицию.

Они хотят найти минимальное время T такое, что каждая команда может двигаться в течении этих T минут, и количество различных городов, в которых окажутся команды, как минимум K (потому что они будут исследовать только город, в котором окажутся в конце). Команда не обязана двигаться все время, если им нравится какой-то город, они могут остаться в нем и подождать, пока время пройдет.

Помогите участникам определить это минимальное время T такое, что участники закончат в минимум K различных городах, или выведите -1, если решения нет.

Обратите внимание, что между некоторыми городами может быть больше одной дороги.

Входные данные

Первая строка содержит четыре целых числа: V, E, N и K (1 ≤  V  ≤  600,  1  ≤  E  ≤  20000,  1  ≤  N  ≤  min(V, 200),  1  ≤  K  ≤  N) — количество городов, количество дорог, количество команд и минимальное количество различных городов, в которых они должны закончить.

Вторая строка содержит N целых чисел — города, в которых команды начнут свой путь.

Следующие E строк содержат информацию о дорогах в следующем формате: Ai Bi Ti (1 ≤ Ai, Bi ≤ V,  1 ≤ Ti ≤ 10000), что означает, что есть дорога, соединяющая города Ai и Bi, и команде нужно Ti минут, чтобы пройти по этой дороге.

Выходные данные

Выведите единственное число — минимальное время, в течение которого команды могут двигаться, чтобы закончить в хотя бы K различных городах, или выведите -1, если решения не существует.

Если решение существует, результат будет не больше 1731311.

Пример
Входные данные
6 7 5 4
5 5 2 2 5
1 3 3
1 5 2
1 6 5
2 5 4
2 6 7
3 4 11
3 5 3
Выходные данные
3
Примечание

В примере три команды начинают из города 5, две начинают из города 2. Если они будут двигаться 3 минуты, то возможно следующее: две команды в городе 2, одна команда в городе 5, одна команда в городе 3, и одна команда в городе 1. Видно, что всего есть четыре города, в которых команды закончили путешествие.