Коровы возвращаются в амбар в конце длинного дня и чувствуют себя усталыми
и голодными.
Ферма состоит из \(N\) пастбищ (\(2 \leq N \leq 50,000\)), последовательно
пронумерованных \(1 \dots N\). Коровы хотят добраться до амбара в пастбище \(N\).
Каждое из остальных \(N-1\) пастбищ содержит ровно 1 корову. Коровы могут двигаться
от пастбища к пастбищу по множеству из \(M\) ненаправленных дорожек
(\(1 \leq M \leq 100,000\)). \(i\)-ая дорожка соединяет пару пастбищ \(a_i\) и \(b_i\),
и требуется \(t_i\) единиц времени для её прохождения. Каждая корова может достичь
амбара, пройдя некоторую последовательность дорожек.
Будучи голодными, коровы заинтересованы в остановках для еды на их пути домой.
К счастью, \(K\) пастбищ содержат стоги сена (\(1 \leq K \leq N\)), \(i\)-ый из этих
стогов сена имеет величину вкусности \(y_i\). Каждая хочет съесть один такой стог
сена по дороге в амбар, но только если время, которое добавиться к её пути, не больше чем вкусность стога, который она съест. Заметим, что корова может съесть не более
одного стога сена. Если на её пути встретятся другие пастбища со стогами, она просто
игнорирует их.
ФОРМАТ ВВОДА (файл dining.in):
Первая строка содержит три разделённых пробелом целых числа
\(N\),
\(M\),
\(K\).
Каждая из последующих
\(M\) строк содержит три целых числа
\(a_i\),
\(b_i\),
\(t_i\),
описывающих дорожку между пастбищами
\(a_i\) и
\(b_i\), на прохождение которой
требуется
\(t_i\) времени (
\(a_i\) и
\(b_i\) отличаются друг от друга, а
\(t_i\) -
положительное целое число не более чем
\(10^4\)).
Каждая из следующих \(K\) строк описывает стог сена двумя целыми числами:
индекс пастбища и вкусность стога (положительное целое число не более \(10^9\)).
Множество стогов сена может располагаться на одном и том же пастбище.
ФОРМАТ ВЫВОДА (файл dining.out):
Вывод должен содержать \(N-1\) строку. Строка \(i\) содержит одно целое число
\(1\), если корова на пастбище \(i\) может посетить пастбище со стогом сена и
съесть это стог и 0, в потивном случае.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5 1
1 4 10
2 1 20
4 2 3
2 3 5
4 3 2
2 7
|
1
1
1
|