Смачний обід#10399

Смачний обід

2 секунди

128 мегабайтів

Складна

Корови повертаються до сараю наприкінці довгого дня, почуваючись втомленими та голодними.

Ферма складається з $n$ пасовищ, зручно пронумерованих від $1$ до $n$ . Усі корови хочуть дістатися сараю, який розташований на пасовищі $n$ . На кожному з інших $n - 1$ n - 1 пасовищ знаходиться одна корова. Корови можуть пересуватися між пасовищами по $m$ неорієнтованих стежках. $i$ -та стежка з'єднує пасовища $a_{i}$ a_i та $b_{i}$ b_i і займає час $t_{i}$ t_i для подолання. Кожна корова може дістатися сараю через деяку послідовність стежок.

Будучи голодними, корови хотіли б зупинитися перекусити на шляху додому. На щастя, $k$ пасовищ містять смачні оберемки сіна, і $i$ -й оберемок сіна має смаковитість $y_{i}$ y_i. Кожна корова готова зупинитися біля одного оберемка сіна на своєму шляху до сараю, але лише якщо це збільшить час її подорожі, порівняно з найкоротшим маршрутом до сараю, не більше ніж на смаковитість того оберемка сіна, який вона відвідає. Зауважте, що корова "офіційно" відвідує щонайбільше один оберемок сіна для перекусу; це нормально, якщо її маршрут проходить через інші пасовища з оберемками сіна — вона просто їх ігнорує.

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

Вхідні дані

Перший рядок містить три цілих числа $n$ , $m$ та $k (2 \leq n \leq 5 \cdot 1 0^{4}, 1 \leq m \leq 1 0^{5}, 1 \leq k \leq n)$ k~(2 \le n \le 5 \cdot 10^4, 1 \le m \le 10^5, 1 \le k \le n). Кожен з наступних $m$ рядків містить три цілих числа $a_{i}$ a_i, $b_{i}$ b_i та $t_{i} (a_{i} \neq = b_{i}, 1 \leq t_{i} \leq 1 0^{4})$ t_i~(a_i \ne b_i, 1 \le t_i \le 10^4), що описують стежку між пасовищами $a_{i}$ a_i та $b_{i}$ b_i, яка займає час $t_{i}$ t_i для подолання.

Кожен з наступних $k$ рядків описує один оберемок сіна і містить два цілих числа: номер пасовища, де він знаходиться, та його смаковитість $y_{i} (1 \leq y_{i} \leq 1 0^{9})$ y_i~(1 \le y_i \le 10^9). Декілька оберемків сіна можуть знаходитися на одному пасовищі.

Вихідні дані

Виведіть $n - 1$ n - 1 рядків. $i$ -й рядок повинен містити $1$ , якщо корова на пасовищі $i$ може зупинитися поласувати якимось оберемком сіна на своєму шляху до сараю, та $0$ в іншому випадку.

Приклади

Приклад 1

Примітка

У цьому прикладі корові на пасовищі $3$ слід зупинитися перекусити, оскільки час її подорожі збільшується лише на $6$ (з $2$ до $8$ ), що не перевищує смаковитість $7$ того оберемка сіна. Корові на пасовищі $2$ , очевидно, слід з'їсти сіно на пасовищі $2$ , оскільки це взагалі не змінює її оптимальний маршрут. Корова на пасовищі $1$ є цікавим випадком: на перший погляд може здатися, що її оптимальний маршрут (довжиною $10$ ) збільшиться занадто сильно, щоб зупинка була вигідною. Однак у неї є маршрут, який робить зупинку заради сіна вигідною: піти на пасовище $4$ , потім на пасовище $2$ (де вона з'їдає сіно), а потім назад на пасовище $4$ .