← 返回题目列表

Codeforces · 827/D

D. 最佳边缘重量

中文机器翻译题面 查看原题

给您一个具有 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