Os verões úmidos e sufocantes da região leiteira de Wisconsin fazem as vacas quererem matar a sede. Farmer John bombeia água clara e fria do estábulo para $N$ tubos ramificados, $(3 \le N \le 99999)$, $N$ ímpar, numerados $1,\ldots,N$. O calor aquece a água ao fluir. Bessie procura a mais fria para aproveitar o clima mais que qualquer outra vaca.

O mapa completo forma uma árvore com raiz na fazenda e exatamente dois tubos saindo de cada ramificação. Surpreendentemente, cada tubo tem exatamente uma unidade de comprimento; todos os $N$ se ligam de algum modo à árvore.

Liste pelo mapa as distâncias do estábulo a cada ramificação e extremidade. Bessie as usará para achar a água mais fria.

A extremidade pode entrar numa ramificação ou ser torneira, e recebe o número do tubo. Há $C$ conexões, $(1 \le C \le N)$, cada uma três inteiros: extremidade $E_{i}$, $(1 \le E_{i} \le N)$, e tubos $B1_{i}$, $B2_{i}$, $(2 \le B1_i \le N; 2 \le B2_i \le N)$. O $1$ liga ao estábulo; sua extremidade fica a distância $1$.

Entrada

• Linha $1$: inteiros $N$, $C$ separados por espaço.

• Linhas $2,\ldots,C+1$: linha $i+1$ descreve ramificação $i$ com três inteiros separados por espaços: $E_{i}$, $B1_{i}$, $B2_{i}$.

Saída

• Linhas $1,\ldots,N$: linha $i$ contém a distância inteira do estábulo à extremidade do tubo $i$.

Exemplos

Entrada 1

5 2
3 5 4
1 2 3

Saída 1

1
2
2
3
3

Observação

A entrada descreve este mapa:

                    +------+
                    | Estábulo |
                    +------+
                       | 1
                       *
                    2 / \ 3
                         *
                      4 / \ 5

O tubo $1$ está sempre a distância $1$. Os $2$, $3$ ligam diretamente a ele, distância $2$. Os $4$, $5$ ligam ao $3$, distância $3$.

Autor do problema: Rob Kolstad, 2008