题目描述

给定一个 $n$ 个点，$m$ 条边的简单无向连通图。对于每条边，我们可以降低或升高它的权（记改变后的权值为 $a$），并保持其他边的权不变，使得这条边存在于这个图的所有最小生成树中。

定义一条边的目标值为满足上述条件的 $a$ 的最大值。若 $a$ 可以任意大，则记它为$-1$。.请对每条边，输出它的目标值。

输入格式

第一行：两个整数 $n$ 和 $m$。 接下来 $m$ 行：每行三个数 $u$，$v$，$w$，表示 $u$ 和 $v$ 间有权大小为 $w$ 的边。

输出格式

共 $m$ 个数字：按给定的边顺序，依次输出它的目标值，用空格分开。

4 6
3 2 9
2 4 15
1 2 8
1 3 5
3 4 4
1 4 14

7 7 8 8 13 4

5 4
2 1 24
5 1 6
1 3 11
4 1 13

-1 -1 -1 -1

3 3
1 2 1
1 3 1
2 3 1

0 0 0

数据范围

• 对于 $50\%$ 的数据，$2 \le n, m \le 2000$；
• 对于 $100\%$ 的数据，$2 \le n, m \le 200000$, $1 \le u, v \le n$, $1 \le w \le 10^9$ .