最小生成树(Minimum Spanning Tree)

题目描述

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

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

输入格式

第一行：两个整数 n 和 m。

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

输出格式

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

样例输入 #1

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

样例输出 #1

7 7 8 8 13 4

样例输入 #2

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

样例输出 #2

-1 -1 -1 -1

样例输入 #3

3 3 1 2 1 1 3 1 2 3 1

样例输出 #3

0 0 0

数据范围

• 对于 50% 的数据，2 ≤ n, m ≤ 2000
• 对于 100% 的数据，2 ≤ n, m ≤ 200000, 1 ≤ u, v ≤ n, 1 ≤ w ≤ 10^9

知识点与难度

本题涉及的知识点从属于 GESP 8级，难度等级：⭐⭐⭐⭐。

测试点分布