Le estati umide e afose della zona casearia del Wisconsin spingono le mucche a dissetarsi. Farmer John pompa acqua limpida e fredda dalla stalla in $N$ tubi ramificati, $(3 \le N \le 99999)$, $N$ dispari, numerati $1,\ldots,N$. Il caldo riscalda l'acqua che scorre. Bessie cerca la più fredda per godersi il tempo più di ogni altra mucca.

La mappa completa forma un albero radicato alla fattoria, con esattamente due tubi uscenti da ogni biforcazione. Sorprendentemente ogni tubo è lungo esattamente un'unità; tutti gli $N$ si connettono in qualche modo all'albero.

Elenca le distanze dalla stalla a ogni biforcazione ed estremità. Bessie le userà per trovare l'acqua più fredda.

L'estremità può entrare in una biforcazione o essere un rubinetto e porta il numero del tubo. Ci sono $C$ connessioni, $(1 \le C \le N)$, ciascuna tre interi: estremità $E_{i}$, $(1 \le E_{i} \le N)$, e tubi $B1_{i}$, $B2_{i}$, $(2 \le B1_i \le N; 2 \le B2_i \le N)$. Il $1$ va alla stalla, la sua estremità dista $1$.

Input

• Riga $1$: interi $N$, $C$ separati da spazio.

• Righe $2,\ldots,C+1$: riga $i+1$ descrive biforcazione $i$ con tre interi separati da spazi: $E_{i}$, $B1_{i}$, $B2_{i}$.

Output

• Righe $1,\ldots,N$: riga $i$ contiene la distanza intera dalla stalla all'estremità del tubo $i$.

Esempi

Input 1

5 2
3 5 4
1 2 3

Output 1

1
2
2
3
3

Nota

L'input descrive questa mappa:

                    +------+
                    | Stalla |
                    +------+
                       | 1
                       *
                    2 / \ 3
                         *
                      4 / \ 5

Il tubo $1$ dista sempre $1$. I $2$, $3$ si collegano direttamente a esso, distanza $2$. I $4$, $5$ si collegano al $3$, distanza $3$.

Autore del problema: Rob Kolstad, 2008