У Вас корок

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

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

Місто складається з перехресть, з'єднаних двосторонніми дорогами, які можна проїхати за певний час. Усі водії починають свій рух на перехрестях (можливо, різних) і закінчують на одному, позначеному як центр міста, перехресті номер $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$ чисел, що описують початкові перехрестя, на яких розташовані машини.

Вихідні дані

Виведіть максимальну кількість водіїв, які зможуть дістатися до центру міста без заторів.

Приклади