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

说明

样例中的道路网络如下图所示：