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

說明

範例中的道路網路如下：