P13548 [OOI 2022] Air Reform

CF1648E

伯兰德是一个拥有发达航空网络的大国。全国共有 $n$ 个城市，这些城市一直由 Berlaflot 航空公司运营。该公司在 $m$ 对城市间运营双向航班，第 $i$ 条航线连接城市 $a_i$ 和 $b_i$，票价为 $c_i$，双向价格相同。 已知通过 Berlaflot 的航班，可以从任意城市到达任意其他城市（可能需要中转）。对于一条由多段航班组成的路径，其总费用等于其中最贵一段的费用。更正式地说，从城市 $t_1$ 到 $t_k$（中转 $k-2$ 次），路径费用为 $t_1$ 到 $t_2$，$t_2$ 到 $t_3$，……，$t_{k-1}$ 到 $t_k$ 这些航班中费用的最大值。当然，所有航段都必须由 Berlaflot 执飞。 最近，S8 Airlines 新进入了伯兰德市场。S8 Airlines 在所有未被 Berlaflot 连接的城市对之间开通了双向航班。也就是说，任意一对城市之间，要么有 Berlaflot 的航班，要么有 S8 Airlines 的航班。 S8 Airlines 的航班费用如下：对于通过 S8 Airlines 连接的城市 $x$ 和 $y$，其票价等于 Berlaflot 网络下 $x$ 和 $y$ 之间所有路径中费用最小的那一条（即路径上的最大航段费用最小）。 已知通过 S8 Airlines 的航班，也可以在所有城市之间互达，且路径费用定义同上，也是路径上最大航段费用。 由于 S8 Airlines 的竞争，Berlaflot 决定进行航空改革，调整自家航班票价：对于 Berlaflot 的第 $i$ 条航班（连接 $a_i$ 和 $b_i$），新票价应等于 S8 Airlines 网络下 $a_i$ 和 $b_i$ 之间的最小路径费用。请帮 Berlaflot 计算每条航班改革后的新票价。

每组测试包含多组数据。第一行包含两个整数 $t$ 和 $g$（$1 \le t \le 10\,000$，$0 \le g \le 8$），分别表示测试组数和当前测试组编号。接下来是 $t$ 组测试数据。 每组测试的第一行包含两个整数 $n$ 和 $m$（$4 \le n \le 200\,000$，$n-1 \le m \le 200\,000$，$m \le \frac{(n-1)(n-2)}{2}$），分别表示城市数量和 Berlaflot 航班数量。 接下来的 $m$ 行，每行三个整数 $a_i, b_i, c_i$（$1 \le a_i, b_i \le n$，$1 \le c_i \le 10^9$），表示第 $i$ 条航班连接的城市和票价。 保证没有航班连接同一个城市，也没有两条航班连接同一对城市。保证 Berlaflot 和 S8 Airlines 的航班网络都连通。 记所有测试数据中 $n$ 的总和为 $N$，$m$ 的总和为 $M$。保证 $N, M \le 200\,000$。

对于每组测试数据，输出 $m$ 个整数，第 $i$ 个为第 $i$ 条 Berlaflot 航班改革后的新票价，按输入顺序输出，空格分隔。

### 说明 在第一个测试样例中，S8 Airlines 会在以下城市对之间开通航班：（1,3）、（1,4）、（2,4）。 城市 1 和 3 之间的 S8 航班费用为 2，因为 Berlaflot 网络下最小路径费用为 2（1-2 票价 1，2-3 票价 2，最大为 2）。 城市 1 和 4 之间的 S8 航班费用为 3，因为 Berlaflot 网络下最小路径费用为 3（1-2 票价 1，2-3 票价 2，3-4 票价 3，最大为 3）。 城市 2 和 4 之间的 S8 航班费用为 3，因为 Berlaflot 网络下最小路径费用为 3（2-3 票价 2，3-4 票价 3，最大为 3）。 航空改革后，Berlaflot 的航线 1-2 的票价变为 3，因为 S8 Airlines 网络下 1 和 2 之间最小路径费用为 3（1-4 票价 3，2-4 票价 3，最大为 3）。 航线 2-3 的票价也变为 3，因为 S8 网络下 2 和 3 的最小路径费用为 3（2-4 票价 3，1-4 票价 3，1-3 票价 2，最大为 3）。 航线 3-4 的票价也变为 3，因为 S8 网络下 3 和 4 的最小路径费用为 3（1-3 票价 2，1-4 票价 3，最大为 3）。 第二个测试样例中，S8 Airlines 会在城市对（1,4）、（2,3）、（2,5）、（3,4）、（3,5）之间开通航班，票价分别为 1、1、2、1、2。 ### 评分说明 本题测试数据分为 8 组。只有通过某组所有测试点，且通过所有必需的前置组，才能获得该组分数。**离线评测**表示该组的评测结果将在比赛结束后公布。有些分组不要求通过样例测试点。 | 组别 | 分值 | $n$ | $N$ | $c_i$ | 必须通过的组 | 备注 | |:----:|:----:|:---:|:---:|:-----:|:------------:|:----:| | 0 | 0 | -- | -- | -- | -- | -- | 样例测试点 | | 1 | 11 | $n \le 10$ | $N \le 10\,000$ | -- | 0 | | | 2 | 10 | $n \le 100$ | $N \le 10\,000$ | -- | 0, 1 | | | 3 | 11 | $n \le 1000$ | $N \le 10\,000$ | $c_i \le 2$ | -- | | | 4 | 12 | $n \le 1000$ | $N \le 10\,000$ | -- | 0, 1, 2 | | | 5 | 12 | -- | -- | -- | -- | -- | 所有测试数据 $m = n-1$ | | 6 | 17 | -- | -- | $c_i \le 2$ | 3 | | | 7 | 10 | -- | -- | $c_i \le 10$ | 3, 6 | | | 8 | 17 | -- | -- | -- | 0--7 | **离线评测** |