У Вас корок#5652

У Вас корок

5 секунд

128 мегабайтів

Дуже складна

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

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

Місто складається з перехресть, з'єднаних двосторонніми дорогами, які можна проїхати за певний час. Усі водії починають свій рух на перехрестях (можливо, різних) і закінчують на одному, позначеному як центр міста, перехресті номер $1$ . Якщо два водії одночасно почнуть рух по одній і тій же дорозі в одному напрямку, виникне затор, і ваша мета буде провалена. Проте водії можуть одночасно проїжджати одне й те саме перехрестя або їхати по одній і тій же дорозі, якщо вони в'їхали на неї в різний час.

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

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

Вхідні дані

Перший рядок містить три числа $n, m$ і $c$ , де $n (1 \leq n \leq 25000)$ n~(1 \le n \le 25000) — кількість перехресть, $m (0 \leq m \leq 50000)$ m~(0 \le m \le 50000) — кількість доріг у місті і $c (0 \leq c \leq 1000)$ c~(0 \le c \le 1000) — кількість водіїв. Кожен з наступних $m$ рядків містить три числа $x_{i}, y_{i}$ x_i, y_i і $t_{i}$ t_i, що описують дорогу, де $x_{i}$ x_i і $y_{i} (1 \leq x_{i}, y_{i} \leq n)$ y_i~(1 \le x_i, y_i \le n) — номери різних перехресть, які з'єднує описана дорога, і $t_{i} (1 \leq t_{i} \leq 10000)$ t_i~(1 \le t_i \le 10000) — час, який потрібен водію, щоб дістатися від початку до кінця дороги в будь-якому напрямку. Гарантується, що можна дістатися до центру з будь-якого перехрестя. Останній рядок містить $c$ чисел, що описують початкові перехрестя, на яких розташовані машини.

Вихідні дані

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

Приклади

Приклад 1

Приклад 2