Octagon é responsável por muitas instalações de importância estratégica, como silos de mísseis, radares, cantinas, gabinetes de veteranos, armazéns de uniformes, … É extremamente importante proteger a rede de ligações entre estas instalações, mas, por outro lado, a ameaça a esta rede deve ser minimizada. Para cada estrada bidirecional que liga instalações diferentes, foi determinado o Coeficiente de Ameaça de Ataque (coloquialmente chamado coeficiente). Johnny, recentemente contratado pela Octagon, consegue, mesmo a meio da noite, calcular um subconjunto de estradas que minimize a soma dos coeficientes e continue a permitir deslocações entre qualquer par de instalações; chamamos estrada essencial a uma estrada que pertence a pelo menos um desses subconjuntos.

No entanto, nada se pode dar como garantido: os coeficientes podem mudar. Como parte da avaliação anual, a Octagon decidiu calcular, para cada estrada, o maior valor de $x$ tal que, ao definir o seu coeficiente como $x$ (mantendo todos os restantes coeficientes como estavam), essa estrada seja essencial. A tarefa foi atribuída a Johnny, que não se pode enganar num assunto tão importante.

Entrada

A primeira linha da entrada contém dois inteiros $n$ e $m$ ($1 \le n \le 100\,000$, $n-1 \le m \le 10^6$), separados por um único espaço, que indicam, respetivamente, o número de instalações sob supervisão da Octagon e o número de estradas bidirecionais entre elas. As instalações estão numeradas com números naturais consecutivos de $1$ a $n$.

Em cada uma das $m$ linhas seguintes existem três inteiros: $a$, $b$ e $c$ ($1 \le a,b \le n$, $a \ne b$, $0 \le c \le 10^9$), separados por um único espaço, que descrevem uma estrada bidirecional entre as instalações $a$ e $b$, com coeficiente $c$. Cada par não ordenado $\{a,b\}$ ocorre no máximo uma vez.

As estradas existentes permitem sempre deslocações entre quaisquer duas instalações.

Saída

Deves escrever $m$ linhas, uma para cada estrada da entrada, pela mesma ordem. Na linha correspondente a uma estrada, deves escrever um número natural: o valor máximo tal que, depois de alterar o coeficiente dessa estrada para esse valor (mantendo os outros coeficientes inalterados), ela seja uma estrada essencial. Se esse valor for superior a $10^9$ ou puder ser arbitrariamente grande, deves escrever $10^9$.

Exemplos

Entrada 1

6 7
1 2 2
2 3 1
3 4 0
1 4 3
3 5 20
4 5 8
3 6 14

Saída 1

3
3
3
2
8
20
1000000000

Nota

A rede de estradas do exemplo é a seguinte: