[AdditionalFile5384.zip](file://AdditionalFile5384.zip?type=additional_file)

#5384. 「OOI 2022 Day 2」航空改革

标签: 传统 | 时间限制: 2000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2022 Day2 T4 「Авиареформа / Air Reform」。

伯兰迪亚是一个拥有发达航空系统的庞大国家。全国共有 $n$ 个城市，历史上由伯兰航空公司提供服务。伯兰航空公司在 $m$ 对城市之间运营双向航班，第 $i$ 个航班连接城市 $a_i$ 和 $b_i$，单程票价为 $c_i$。

已知通过伯兰航空的航班，可以从任意城市到达任意其他城市（可能需要中转），并且任何由多个中转航班组成的路线的成本等于其中最贵的航班的成本。更正式地说，从城市 $t_1$ 到城市 $t_k$ 的路线，若有 $(k-2)$ 次中转经过城市 $t_2, t_3, t_4, \ldots, t_{k-1}$，则该路线的成本为从 $t_1$ 到 $t_2$、$t_2$ 到 $t_3$、$t_3$ 到 $t_4$ 等直到 $t_{k-1}$ 到 $t_k$ 的所有航班成本的最大值。当然，所有这些航班必须由伯兰航空运营。

最近，伯兰迪亚新成立了一家航空公司 S8 航空。该公司在所有没有伯兰航空航班的城市对之间运营双向航班。因此，每对城市之间要么有伯兰航空的航班，要么有 S8 航空的航班。

S8 航空的航班价格计算如下：对于每对运营 S8 航空航班的城市 $x$ 和 $y$，该航班的成本等于伯兰航空从 $x$ 到 $y$ 的最低路线成本（按照上述成本计算规则）。

已知通过 S8 航空的航班，可以从任意城市到达任意其他城市（可能需要中转），并且与伯兰航空类似，S8 航空的多段中转路线的成本等于其中最贵的航班的成本。

由于与 S8 航空的竞争加剧，伯兰航空决定进行航空改革，调整其航班价格。具体来说，对于连接城市 $a_i$ 和 $b_i$ 的第 $i$ 个航班，伯兰航空希望将其价格调整为 S8 航空从 $a_i$ 到 $b_i$ 的最低路线成本。请帮助伯兰航空的经理计算新的航班价格。

输入格式

每个测试点包含多组输入数据。第一行包含两个整数 $t$ 和 $g$ $(1 \leq t \leq 10000, 0 \leq g \leq 8)$，分别表示输入数据的组数和子任务编号。接下来是各组数据的描述。

每组数据的第一行包含两个整数 $n$ 和 $m$ $(4 \leq n \leq 200000, n-1 \leq m \leq 200000, m \leq \frac{(n-1)(n-2)}{2})$，分别表示伯兰迪亚的城市数量和伯兰航空的航班数量。

接下来的 $m$ 行描述伯兰航空的航班，第 $i$ 行包含三个整数 $a_i, b_i, c_i$ $(1 \leq a_i, b_i \leq n, 1 \leq c_i \leq 10^{9})$，表示第 $i$ 个航班连接的城市编号和该航班的成本。

保证没有航班连接同一城市自身，也没有两条航班连接同一对城市。保证通过伯兰航空的航班可以从任意城市到达任意其他城市，并且通过 S8 航空的航班也可以从任意城市到达任意其他城市。

设 $N$ 表示所有数据组中 $n$ 的总和，$M$ 表示所有数据组中 $m$ 的总和。保证 $N, M \leq 200000$。

输出格式

对于每组输入数据，在单独的一行中输出 $m$ 个整数，其中第 $i$ 个整数表示航空改革后第 $i$ 个伯兰航空航班的成本。

样例

输入

3 0
4 3
1 2 1
2 3 2
4 3 3
5 5
1 2 1
1 3 1
2 4 1
4 5 2
5 1 3
6 6
1 2 3
2 3 1
3 6 5
3 4 2
4 5 4
2 4 2

输出

3 3 3
1 1 1 2 2
4 4 5 3 4 4

在第一组输入数据中，S8 航空将在以下城市对之间运营航班：$(1, 3)$、$(1, 4)$ 和 $(2, 4)$。

• 城市 $1$ 和 $3$ 之间航班的成本为 $2$，因为伯兰航空的最低路线成本为 $2$——路线包括城市 $1$ 到 $2$ 的航班（成本 $1$）和城市 $2$ 到 $3$ 的航班（成本 $2$），最大值为 $2$。
• 城市 $1$ 和 $4$ 之间航班的成本为 $3$，因为伯兰航空的最低路线成本为 $3$——路线包括城市 $1$ 到 $2$ 的航班（成本 $1$）、城市 $2$ 到 $3$ 的航班（成本 $2$）和城市 $3$ 到 $4$ 的航班（成本 $3$），最大值为 $3$。
• 城市 $2$ 和 $4$ 之间航班的成本为 $3$，因为伯兰航空的最低路线成本为 $3$——路线包括城市 $2$ 到 $3$ 的航班（成本 $2$）和城市 $3$ 到 $4$ 的航班（成本 $3$），最大值为 $3$。

航空改革后：

• 伯兰航空城市 $1$ 和 $2$ 之间航班的成本将为 $3$，因为 S8 航空的最低路线成本为 $3$——路线包括城市 $1$ 到 $4$ 的航班（成本 $3$）和城市 $2$ 到 $4$ 的航班（成本 $3$），最大值为 $3$。
• 伯兰航空城市 $2$ 和 $3$ 之间航班的成本将为 $3$，因为 S8 航空的最低路线成本为 $3$——路线包括城市 $2$ 到 $4$ 的航班（成本 $3$）、城市 $1$ 到 $4$ 的航班（成本 $3$）和城市 $1$ 到 $3$ 的航班（成本 $2$），最大值为 $3$。
• 伯兰航空城市 $3$ 和 $4$ 之间航班的成本将为 $3$，因为 S8 航空的最低路线成本为 $3$——路线包括城市 $1$ 到 $3$ 的航班（成本 $2$）和城市 $1$ 到 $4$ 的航班（成本 $3$），最大值为 $3$。

在第二组输入数据中，S8 航空将运营以下航班：城市 $1$ 和 $4$ 之间（成本 $1$）、城市 $2$ 和 $3$ 之间（成本 $1$）、城市 $2$ 和 $5$ 之间（成本 $2$）、城市 $3$ 和 $4$ 之间（成本 $1$）、城市 $3$ 和 $5$ 之间（成本 $2$）。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。