CF1648E Air Reform

可以在 [P13548](https://www.luogu.com.cn/problem/P13548) 评测本题。

伯兰德是一个拥有发达航空网络的大国。全国共有 $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$（$1 \le t \le 10\,000$），表示测试组数。接下来是 $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。