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