Octagon ist für viele strategisch wichtige Einrichtungen zuständig, etwa Raketensilos, Radaranlagen, Kantinen, Veteranenbüros, Uniformlager, … Es ist äußerst wichtig, das Verbindungsnetz zwischen diesen Einrichtungen zu sichern; andererseits soll die Bedrohung dieses Netzes minimiert werden. Für jede in beide Richtungen befahrbare Straße zwischen verschiedenen Einrichtungen wurde ein Angriffsbedrohungskoeffizient (umgangssprachlich der Koeffizient) festgelegt. Johnny, der kürzlich von Octagon eingestellt wurde, kann sogar mitten in der Nacht eine Teilmenge der Straßen berechnen, die die Summe der Koeffizienten minimiert und weiterhin das Reisen zwischen jedem Paar von Einrichtungen ermöglicht; eine Straße, die in mindestens einer solchen Teilmenge liegt, nennen wir Schlüsselstraße.

Allerdings ist nichts selbstverständlich: Koeffizienten können sich ändern. Im Rahmen der jährlichen Bewertung beschloss Octagon, für jede Straße den größten Wert von $x$ zu berechnen, sodass diese Straße eine Schlüsselstraße ist, wenn ihr Koeffizient auf $x$ gesetzt wird (und alle anderen Koeffizienten unverändert bleiben). Diese Aufgabe wurde Johnny übertragen, der sich bei einer so wichtigen Angelegenheit nicht irren darf.

Eingabe

Die erste Eingabezeile enthält zwei durch ein einzelnes Leerzeichen getrennte ganze Zahlen $n$ und $m$ ($1 \le n \le 100\,000$, $n-1 \le m \le 10^6$), die jeweils die Anzahl der Einrichtungen unter Octagons Aufsicht und die Anzahl der in beide Richtungen befahrbaren Straßen zwischen ihnen angeben. Die Einrichtungen sind mit aufeinanderfolgenden natürlichen Zahlen von $1$ bis $n$ nummeriert.

In jeder der folgenden $m$ Zeilen stehen drei ganze Zahlen $a$, $b$ und $c$ ($1 \le a,b \le n$, $a \ne b$, $0 \le c \le 10^9$), jeweils durch ein einzelnes Leerzeichen getrennt. Sie beschreiben eine in beide Richtungen befahrbare Straße zwischen den Einrichtungen $a$ und $b$ mit Koeffizient $c$. Jedes ungeordnete Paar $\{a,b\}$ kommt höchstens einmal vor.

Die vorhandenen Straßen ermöglichen stets das Reisen zwischen zwei beliebigen Einrichtungen.

Ausgabe

Gib $m$ Zeilen aus, eine für jede Straße der Eingabe, in derselben Reihenfolge wie in der Eingabe. In der Zeile für eine bestimmte Straße soll eine natürliche Zahl stehen: der größte Wert, sodass diese Straße nach Änderung ihres Koeffizienten auf diesen Wert (bei unveränderten anderen Koeffizienten) eine Schlüsselstraße ist. Falls dieser Wert größer als $10^9$ ist oder beliebig groß sein kann, gib $10^9$ aus.

Beispiele

Eingabe 1

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

Ausgabe 1

3
3
3
2
8
20
1000000000

Hinweis

Das Straßennetz aus dem Beispiel sieht folgendermaßen aus: