Octagon 負責好多有戰略重要性嘅設施，例如導彈發射井、雷達、飯堂、退伍軍人辦公室、制服倉庫等等。確保呢啲設施之間嘅連接網絡安全係極之重要嘅，但另一方面，亦應該將呢個網絡受到嘅威脅減到最低。每條連接唔同設施嘅雙向道路都有一個攻擊威脅係數（平時簡稱係數）。最近先受僱於 Octagon 嘅 Johnny 就算半夜都可以計到一個道路子集，令係數總和最細，同時仍然可以喺任意一對設施之間通行；我哋將至少屬於一個咁嘅子集嘅道路叫做關鍵道路。

不過，冇嘢係必然嘅——係數可能會變。作為年度評估嘅一部分，Octagon 決定對每條道路計最大嘅 $x$，令到將佢嘅係數設為 $x$（其餘所有係數保持原值）之後，呢條道路仍然係關鍵道路。呢個任務交咗畀 Johnny；咁重要嘅事，佢唔可以出錯。

輸入格式

輸入第一行有兩個用一個空格分隔嘅整數 $n$ 同 $m$（$1 \le n \le 100\,000$，$n-1 \le m \le 10^6$），分別表示 Octagon 管轄嘅設施數量同設施之間嘅雙向道路數量。設施用由 $1$ 到 $n$ 嘅連續自然數編號。

跟住 $m$ 行，每行有三個用一個空格分隔嘅整數 $a$、$b$ 同 $c$（$1 \le a,b \le n$，$a \ne b$，$0 \le c \le 10^9$），描述一條連接設施 $a$ 同 $b$、係數係 $c$ 嘅雙向道路。每個無序對 $\{a,b\}$ 最多出現一次。

現有道路保證任意兩個設施之間都可以通行。

輸出格式

你要輸出 $m$ 行，跟返輸入嘅道路順序，每條道路對應一行。喺對應某條道路嗰行，輸出一個自然數，表示將條路嘅係數改成呢個值（其他係數保持不變）之後，條路仍然係關鍵道路嘅最大值。如果呢個值大過 $10^9$ 或者可以任意大，就輸出 $10^9$。

樣例

輸入格式 1

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

輸出格式 1

3
3
3
2
8
20
1000000000

說明

樣例入面嘅道路網絡如下：