Octagon は、ミサイル発射施設、レーダー、食堂、退役軍人の事務所、制服倉庫など、戦略上重要な多くの施設を管理しています。これらの施設間の接続網を安全にすることは非常に重要ですが、一方で、この網に対する脅威も最小限にする必要があります。異なる施設を結ぶ各双方向道路には、攻撃脅威係数（通称、係数）が定められています。最近 Octagon に雇われた Johnny は、真夜中でも、係数の総和を最小にし、かつ任意の 2 施設間を移動できる道路の部分集合を計算できます。このような部分集合の少なくとも 1 つに含まれる道路を重要道路と呼びます。

しかし、何事も当然とは限りません。係数は変わる可能性があります。年次評価の一環として、Octagon は各道路について、その係数を $x$ に設定し（他のすべての係数は元のまま）、その道路が重要道路となるような $x$ の最大値を計算することにしました。この仕事は Johnny に任されました。これほど重要な件で彼は間違えるわけにはいきません。

入力

入力の最初の行には、空白 1 つで区切られた 2 つの整数 $n$ と $m$ ($1 \le n \le 100\,000$, $n-1 \le m \le 10^6$) が与えられ、それぞれ Octagon の管理下にある施設数と、それらの間の双方向道路数を表します。施設には $1$ から $n$ までの連続した自然数が割り当てられています。

続く $m$ 行には、それぞれ空白 1 つで区切られた 3 つの整数 $a$、$b$、$c$ ($1 \le a,b \le n$, $a \ne b$, $0 \le c \le 10^9$) が与えられ、施設 $a$ と $b$ を結ぶ係数 $c$ の双方向道路を表します。どの順序なし対 $\{a,b\}$ も高々 1 回しか現れません。

既存の道路を使って、任意の 2 施設間を移動することが必ずできます。

出力

入力と同じ道路の順序で、各道路について 1 行ずつ、計 $m$ 行を出力してください。ある道路に対応する行には、その係数をその値に変更し（他の係数は変えずに）、その道路が重要道路となるような最大値を自然数 1 つで出力してください。この値が $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

注記

例の道路網は次のとおりです。