Octagon zarządza wieloma obiektami o znaczeniu strategicznym, takimi jak silosy rakietowe, radary, stołówki, biura weteranów, magazyny mundurów, … Zapewnienie bezpieczeństwa sieci połączeń między tymi obiektami jest niezwykle ważne, ale z drugiej strony zagrożenie dla tej sieci należy zminimalizować. Dla każdej dwukierunkowej drogi łączącej różne obiekty określono Współczynnik Zagrożenia Atakiem (potocznie nazywany współczynnikiem). Johnny, niedawno zatrudniony przez Octagon, nawet w środku nocy potrafi wyznaczyć podzbiór dróg minimalizujący sumę współczynników i nadal pozwalający przemieszczać się między dowolną parą obiektów; drogę należącą do co najmniej jednego takiego podzbioru nazywamy drogą kluczową.

Jednak niczego nie można brać za pewnik — współczynniki mogą się zmieniać. W ramach corocznej oceny Octagon postanowił dla każdej drogi obliczyć największą wartość $x$ taką, że po ustawieniu jej współczynnika na $x$ (i pozostawieniu wszystkich pozostałych współczynników bez zmian) droga ta jest kluczowa. Zadanie przydzielono Johnny’emu, który nie może się pomylić w tak ważnej sprawie.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $n$ i $m$ ($1 \le n \le 100\,000$, $n-1 \le m \le 10^6$), oddzielone pojedynczą spacją, oznaczające odpowiednio liczbę obiektów pod nadzorem Octagonu i liczbę dwukierunkowych dróg między nimi. Obiekty ponumerowano kolejnymi liczbami naturalnymi od $1$ do $n$.

W każdym z kolejnych $m$ wierszy są trzy liczby całkowite: $a$, $b$ i $c$ ($1 \le a,b \le n$, $a \ne b$, $0 \le c \le 10^9$), oddzielone pojedynczymi spacjami, opisujące dwukierunkową drogę między obiektami $a$ i $b$ o współczynniku $c$. Każda nieuporządkowana para $\{a,b\}$ występuje co najwyżej raz.

Istniejące drogi zawsze pozwalają przemieszczać się między dowolnymi dwoma obiektami.

Wyjście

Należy wypisać $m$ wierszy, po jednym dla każdej drogi z wejścia, w tej samej kolejności. W wierszu odpowiadającym danej drodze należy wypisać jedną liczbę naturalną — największą wartość taką, że po zmianie współczynnika tej drogi na tę wartość (i pozostawieniu pozostałych współczynników bez zmian) droga ta jest kluczowa. Jeśli wartość ta jest większa niż $10^9$ lub może być dowolnie duża, należy wypisać $10^9$.

Przykład

Wejście 1

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

Wyjście 1

3
3
3
2
8
20
1000000000

Uwagi

Sieć dróg z przykładu wygląda następująco: