给您一个具有 n 个顶点和 m 个边的连通加权图。该图不包含循环或多重边。考虑一些 id 为 i 的边。让我们确定这条边的最大整数权重,以便在不更改其他权重的情况下,它包含在图的所有最小生成树中。
您需要确定上述每条边的最大重量。您应该独立计算每条边的答案,这意味着不能有两条边同时改变权重。
输入
第一行包含两个整数 n 和 m (2 ≤ n ≤ 2·105, n - 1 ≤ m ≤ 2·105),其中 n 和 m 分别是图中的顶点数和边数。
接下来的 m 行中的每一行都包含三个整数 u、v 和 c (1 ≤ v, u ≤ n, v ≠ u, 1 ≤ c ≤ 109),这意味着顶点 u 和 v 之间存在一条权重为 c 的边。
输出
按照输入中给出的边的顺序打印每条边的答案。如果任意权重的每个最小生成树中都包含一条边,则打印 -1 作为答案。
示例
输入 #1
4 4 1 2 2 2 3 2 3 4 2 4 1 3
输出 #1
2 2 2 1
输入 #2
4 3 1 2 2 2 3 2 3 4 2
输出 #2
-1 -1 -1