Desvio

Na cidade de Nlogonia, o prefeito finalmente vai cumprir sua promessa de campanha e irá repavimentar alguns trechos de ruas. Contudo, enquanto um trecho estiver sendo repavimentado, os carros não poderão usá-lo e portanto um desvio deve ser utilizado.

Cada trecho de rua conecta duas esquinas na cidade, tem comprimento positivo e pode ser percorrido em ambas as direções.

Um desvio é um caminho alternativo que pode servir como um substituto temporário para o trecho de rua em obras. Mais especificamente, se o trecho que conecta as esquinas $U$ e $V$ estiver interditado, o desvio deve ser uma sequência de trechos de ruas que começa em $U$ , termina em $V$ , e não usa o trecho que conecta $U$ diretamente com $V$. O objetivo é encontrar o desvio mais curto para cada trecho, de forma a minimizar o impacto enquanto as obras estiverem sendo feitas.

Como Integrante do Centro de Pavimentação e Carros, você deve ajudar o prefeito a calcular qual é o comprimento do desvio mais curto, para cada trecho.

A primeira linha contém dois inteiros, $N$ e $M$ $(1 ≤ N ≤ 300)$, que representam, respectivamente, o número de esquinas e o número de trechos de ruas. Cada uma das $M$ linhas seguintes contém três inteiros: $U$ , $V$ , e $L$ $(1 ≤ U ≤ N , 1 ≤ V ≤ N , U ̸= V , 1 ≤ L ≤ 10^6 )$, que representam um trecho de mão dupla de comprimento $L$ que liga as esquinas $U$ e $V$ . Nenhum trecho de rua é representado mais de uma vez.

Imprima $M$ linhas, onde cada linha contém um inteiro. O i-ésimo inteiro deve ser o comprimento do desvio mais curto para o i-ésimo trecho, ou -1 se não for possı́vel fazer um desvio. A ordem dos trechos na saída deve ser a mesma ordem fornecida na entrada.