Задача с. Дед Максим собирается в путешествие по Флатландии. К сожалению, из доступных средств
передвижения у него есть только мопед, запас хода которого ограничен. Более точно, если бак
мопеда полностью заполнен, то мопед может проехать не более 3 километров без дополнительной
дозаправки.
Всего во Флатландии есть п городов, пронумерованных от 1 до п. В некоторых городах находятся
заправки, и если в городе есть заправка, то в этом городе дед Максим может полностью наполнить
бак. К сожалению, заправки присутствуют лишь в городах. Также во Флатландии есть т дорог,
i-я из которых соединяет города vi и ui , и имеет длину сi километров. По каждой дороге можно
перемещаться в обоих направлениях.
Дед Максим начинает свое путешествие в городе с номером 1 с полным баком (в городе 1 есть
заправка ему определить, до каких городов он сможет добраться на мопеде.
Формат входных данных
В первой строке записаны четыре целых числа n, m,k, s (1 < n< 150 000,0 m < 150 000,
1 В следующих т строках записаны по три целых числа и, v, ca (1 < ui, va < n, u + vi,
1 < c соединяющих одинаковую пару городов.
В следующей строке записаны к целых чисел р. (1 р < n) номера городов с заправками.