У Вас пробка

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

К сожалению, из-за того что водители эгоистичны, они никогда не поедут по не самому короткому из возможных путей в центр, даже если вы попросите их об этом. Вы можете только советовать им, какой из нескольких кратчайших путей выбрать.

Город состоит из перекрестков, соединенных двухсторонними дорогами, которые можно проехать за заданное время. Все водители начинают свое движение на перекрестках (возможно, различных) и заканчивают на одном обозначенном как центр города перекрестке номер $1$. Если два водителя одновременно начнут движение по одной и той же дороге в одном направлении, то возникнет пробка и ваша цель будет провалена. Однако водители могут проезжать один и тот же перекресток одновременно или ехать по одной и той же дороге, въехав на нее в разное время.

Определите максимальное количество водителей, которые могут добраться в центр города без пробок, если все водители начинают свое движение одновременно и ни один из них не поедет по неоптимальному пути.

На рисунке C.1 машины изображены в их начальном расположении. Один водитель уже находится в центре, а из машин, находящихся на $4$ перекрестке, одна может двигаться вдоль пунктирной линии через перекресток $3$, другая — вдоль пунктирной линии через перекресток $2$, но оставшиеся две не смогут добраться до центра без пробок. Таким образом, ответ на этот тест будет $3$.

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

Первая строка содержит три числа $n,m$ и $c$, где $n(1\le n\le 25000)$ — количество перекрестков, $m(0\le m\le 50000)$ — количество дорог в городе и $c(0\le c\le 1000)$ — количество водителей. Каждая из следующих $m$ строк содержит три числа $x_i,y_i$ и $t_i$, описывающие дорогу, где $x_i$ и $y_i(1\le x_i,y_i\le n)$ — номера различных перекрестков, которые соединяет описанная дорога и $t_i(1\le t_i\le 10000)$ — время, которое должен потратить водитель чтобы добраться от начала до конца дороги в любом направлении. Гарантируется, что можно добраться в центр с любого перекрестка. Последняя строка содержит c чисел, описывающих начальные перекрестки, на которых расположены машины.

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

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

Примеры