Вишукана кухня
Корови повертаються до хліва наприкінці довгого дня і почуваються втомленими та голодними.
Ферма складається з n пасовищ, пронумерованих послідовно від 1 до n. Корови прагнуть дістатися до хліва на пасовищі n. Кожне з решти n − 1 пасовищ містить рівно 1 корову. Корови можуть пересуватися між пасовищами за допомогою m ненаправлених доріжок. i-а доріжка з'єднує пару пасовищ a[i] і b[i], і для її проходження потрібно t[i] одиниць часу. Кожна корова може дістатися до хліва, пройшовши певну послідовність доріжок.
Будучи голодними, корови зацікавлені в зупинках для їжі на своєму шляху додому. На щастя, k пасовищ містять стоги сіна, і i-ий з цих стогів має величину смачності y[i]. Кожна корова хоче з'їсти один такий стіг сіна по дорозі до хліва, але тільки якщо додатковий час, витрачений на це, не перевищує смачність стога, який вона з'їсть. Зауважте, що корова може з'їсти не більше одного стога сіна. Якщо на її шляху зустрінуться інші пасовища зі стогами, вона просто ігнорує їх.
Вхідні дані
Перший рядок містить три розділених пробілом цілі числа n (2 ≤ n ≤ 50000), m (1 ≤ m ≤ 10^5), k (1 ≤ k ≤ n). Кожен з наступних m рядків містить три цілі числа a[i], b[i], t[i], що описують доріжку між пасовищами a[i] і b[i], на проходження якої потрібно t[i] часу (a[i] і b[i] відрізняються один від одного, а t[i] - додатнє ціле число не більше ніж 10^4).
Кожен з наступних k рядків описує стіг сіна двома цілими числами: індекс пасовища і смачність стога (додатнє ціле число не більше 10^9). Множина стогів сіна може розташовуватися на одному і тому ж пасовищі.
Вихідні дані
Вивід повинен містити n − 1 рядок. Рядок i містить одне ціле число 1, якщо корова на пасовищі i може відвідати пасовище зі стогом сіна і з'їсти цей стіг, і 0 в протилежному випадку.
Приклад
У цьому прикладі корова на пасовищі 3 повинна зупинитися для їжі, оскільки її маршрут збільшиться лише на 6 (з 2 до 8), а вона з'їсть стіг смачності 7 (6 <= 7). Корова на пасовищі 2 повинна з'їсти стіг на пасовищі 2. Корова на пасовищі 1 - цікавий випадок, оскільки вона може пройти по своєму оптимальному маршруту (довжиною 10), однак насправді вона має вигідний маршрут з їжею - спочатку на пасовище 4, потім на пасовище 2 (їсти стіг), потім знову на пасовище 4.