Vacas Jantando

As vacas estão voltando para o celeiro no final de um longo dia, sentindo-se cansadas e famintas.
A fazenda consiste em $$N$$ pastos $$(2 \leq N \leq 5 \cdot 10^4)$$, convenientemente numeradas $$[1, N]$$. Todas as vacas querem viajar para o celeiro no pasto $$N$$. Cada um dos outros pastos $$N-1$$ contém uma vaca. As vacas podem se mover de pastagem para pasto através de um conjunto de $$M$$ trilhas não direcionadas $$(1 \leq M \leq 10^5)$$. O $$i$$-ésimo caminho conecta um par de pastos $$a_i$$ e $$b_i$$, e requer tempo para atravessar. Cada vaca pode chegar ao celeiro através de uma sequência de trilhas.

Estar com fome, as vacas estão interessadas em potencialmente parar por comida a caminho de casa. Convenientemente, K dos pastos contém saborosos fardos de feno $$(1 \leq K \leq N)$$, com o $$i$$-ésimo fardo de feno tendo um “sabor” de $$y_i$$ (valor que mede o sabor do prato). Cada vaca está disposta a parar em um único feno ao longo de sua viagem para o celeiro, mas somente se a quantidade de tempo que isso adiciona ao seu caminho é, no máximo, o “sabor” do feno que ela visita. Note que uma vaca só “oficialmente” visita no máximo um feno para jantar, embora seja bom que o caminho dela a leve através de outras pastagens contendo fardos de feno; ela simplesmente ignora isso.

Entrada

A primeira linha contém três inteiros separados por espaço $$N$$, $$M$$ e $$K$$. Cada uma das próximas $$M$$ linhas contém três inteiros $$a_i$$, $$b_i$$ e $$t_i$$, descrevendo um rastro entre pastagens $$a_i$$ e $$b_i$$ que leva o tempo a ser percorrido ($$a_i$$ e $$b_i$$ são diferentes um do outro, e $$t_i$$ é um inteiro positivo no máximo $$10^4$$).
As próximas $$K$$ linhas descrevem um fardo de feno em termos de dois inteiros: o índice de seu pasto e seu “sabor” (um inteiro positivo no máximo $$10^9$$). Vários fardos de feno podem residir no mesmo pasto.

Saída

A saída deve consistir em $$N – 1$$ linhas. A linha $$i$$ contém o único inteiro $$1$$ se a vaca no $$i$$-ésimo pasto pode visitar e comer em algum fardo de feno no caminho para o celeiro, e $$0$$ caso contrário.

Exemplos

4 5 1
1 4 10
2 1 20
4 2 3
2 3 5
4 3 2
2 7

1
1
1