Коровы возвращаются в амбар в конце длинного дня и чувствуют себя усталыми и голодными.

Ферма состоит из n пастбищ, последовательно пронумерованных 1..n. Коровы хотят добраться до амбара в пастбище n. Каждое из остальных n − 1 пастбищ содержит ровно 1 корову. Коровы могут двигаться от пастбища к пастбищу по множеству из m ненаправленных дорожек. i-ая дорожка соединяет пару пастбищ ai и bi, и требуется ti единиц времени для её прохождения. Каждая корова может достичь амбара, пройдя некоторую последовательность дорожек.

Будучи голодными, коровы заинтересованы в остановках для еды на их пути домой. К счастью, k пастбищ содержат стоги сена, i-ый из этих стогов сена имеет величину вкусности yi. Каждая хочет съесть один такой стог сена по дороге в амбар, но только если время, которое добавиться к её пути, не больше чем вкусность стога, который она съест. Заметим, что корова может съесть не более одного стога сена. Если на её пути встретятся другие пастбища со стогами, она просто игнорирует их.

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

Первая строка содержит три разделённых пробелом целых числа n (2 ≤ n ≤ 50000), m (1 ≤ m ≤ 105), k (1 ≤ k ≤ n). Каждая из последующих m строк содержит три целых числа ai, bi, ti, описывающих дорожку между пастбищами ai и bi, на прохождение которой требуется ti времени (ai и bi отличаются друг от друга, а ti - положительное целое число не более чем 104).

Каждая из следующих k строк описывает стог сена двумя целыми числами: индекс пастбища и вкусность стога (положительное целое число не более 109). Множество стогов сена может располагаться на одном и том же пастбище.

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

Вывод должен содержать n − 1 строку. Строка i содержит одно целое число 1, если корова на пастбище i может посетить пастбище со стогом сена и съесть это стог и 0 в потивном случае.

Пример

В этом примере корова в пастбище 3 должна остановится для еды, поскольку её маршрут увеличится только на 6 (с 2 до 8), а она съест стог вкусности 7 (6 <= 7). Корова в пастбище 2 должна съесть стог в пастбище 2. Корова в пастбище 1 - интересный случай поскольку она может пройти по своему оптимальному маршруту (длиной 10), однако в действительности она имеет выгодный маршрут с едой - сначала в пастбище 4, затем в пастбище 2 (кушать стог), затем опять в пастбище 4.