← 返回题目列表

Codeforces · 1648/E

E. 空气改造

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

柏林是一个拥有发达航空公司的大国。 Berlaflot 航空公司历史上曾为该国的 $$$n$$$ 个城市提供服务。该航空公司在 $$$m$$$ 城市之间运营双向航班,其中 $$$i$$$-th 连接编号为 $$$a_i$$$ 和 $$$b_i$$$ 的城市,并且双向航班的价格为 $$$c_i$$$。

众所周知,Berlaflot 航班可用于从任何城市前往任何其他城市(可能需要转机),并且由多个后续航班组成的任何航线的费用等于其中最昂贵的航班的费用。更正式地说,从城市 $$$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$$$ 的航班。当然,所有这些航班都必须由 Berlaflot 运营。

一家新航空公司 S8 Airlines 最近开始在 Berland 运营。该航空公司提供往返于 Berlaflot 直飞航班未连接的所有城市之间的双向航班。因此,每对城市之间都有 Berlaflot 或 S8 Airlines 的航班。

S8 航空航班的费用计算如下:对于 S8 航空航班连接的每对城市 $$$x$$$ 和 $$$y$$$,该航班的费用等于 Berlaflot 城市 $$$x$$$ 和 $$$y$$$ 之间航线的最低费用,根据前面所述的定价。

众所周知,借助 S8 航空航班,您可以通过可能的转机从任何城市前往任何其他城市,并且与 Berlaflot 类似,由多个 S8 航空航班组成的任何两个城市之间的航线费用等于最昂贵航班的费用。

由于与 S8 航空公司的竞争加剧,Berlaflot 决定进行航空改革并改变其航班成本。也就是说,对于城市 $$$a_i$$$ 和 $$$b_i$$$ 之间的第 $$$i$$$ 航班,Berlaflot 希望使该航班的费用等于 S8 Airlines 城市 $$$a_i$$$ 和 $$$b_i$$$ 之间的航线的最低费用。帮助 Berlaflot 经理计算新的航班成本。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10\,000$$$) - 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$4 \le n \le 200\,000$$$, $$$n - 1 \le m \le 200\,000$$$, $$$m \le \frac{(n - 1) (n - 2)}{2}$$$) — 金额Berland 的城市以及 Berlaflot 的航班数量。

接下来的 $$$m$$$ 行包含 Berlaflot 航班的描述。第 $$$i$$$ 行包含三个整数 $$$a_i$$$、$$$b_i$$$ 和 $$$c_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$1 \le c_i \le 10^9$$$) - 与第 $$$i$$$ 第 $$$i$$$ 航班相连的城市数量以及$$$i$$$第 Berlaflot 航班。

保证没有航班连接一个城市与其本身,没有两个航班连接同一对城市。我们保证,通过使用 Berlaflot 航班,可以从任何城市前往任何其他城市;通过使用 S8 Airlines 航班,可以从任何城市前往任何其他城市。

令 $$$N$$$ 为所有测试用例的 $$$n$$$ 之和,$$$M$$$ 为所有测试用例的 $$$m$$$ 之和。保证$$$N,M \le 200\,000$$$。

输出

对于每个测试用例,您应该在一行中打印 $$$m$$$ 整数,其中 $$$i$$$-th 应该是空中改革后第 $$$i$$$-th Berlaflot 航班的价格。

示例

输入 #1

3
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

输出 #1

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

注意

在第一个测试用例中,S8 航空将提供以下城市对之间的航班:$$$(1, 3)$$$、$$$(1, 4)$$$ 和 $$$(2, 4)$$$。

城市 $$$1$$$ 和 $$$3$$$ 之间的航班费用将等于 $$$2$$$,因为 Berlaflot 航线的最低费用为 $$$2$$$ — 该航线包括城市 $$$1$$$ 和 $$$2$$$ 之间的航班,费用为 $$$1$$$ 以及城市 $$$2$$$ 和 $$$2$$$ 之间的航班$$$3$$$ 成本为$$$2$$$,最大成本为$$$2$$$。

城市 $$$1$$$ 和 $$$4$$$ 之间的航班费用为 $$$3$$$,因为 Berlaflot 航线的最低费用为 $$$3$$$ — 该航线包括城市 $$$1$$$ 和 $$$2$$$ 之间的航班,费用为 $$$1$$$,城市 $$$2$$$ 和 $$$3$$$ 之间的航班费用为 $$$2$$$,城市 $$$3$$$ 和 $$$4$$$ 之间的航班费用为 $$$3$$$,最高费用为 $$$3$$$。

城市 $$$2$$$ 和 $$$4$$$ 之间的航班费用将为 $$$3$$$,因为 Berlaflot 航线的最低费用为 $$$3$$$ — 该航线包括城市 $$$2$$$ 和 $$$3$$$ 之间的航班,费用为 $$$2$$$ 以及城市 $$$3$$$ 和 $$$4$$$ 之间的航班成本为$$$3$$$,最大成本为$$$3$$$。

航空改革后,$$$1$$$ 和 $$$2$$$ 城市之间的 Berlaflot 航班费用将为 $$$3$$$,因为这些城市之间的 S8 航空航线的最低费用为 $$$3$$$ — 该航线包括 $$$1$$$ 和 $$$4$$$ 城市之间的航班,费用为 $$$3$$$ 以及城市之间的航班$$$2$$$ 和 $$$4$$$ 成本为 $$$3$$$,最大成本为 $$$3$$$。

城市 $$$2$$$ 和 $$$3$$$ 之间的 Berlaflot 航班费用将为 $$$3$$$,因为 S8 Airlines 往返这些城市的航线的最低费用为 $$$3$$$ — 该航线包括城市 $$$2$$$ 和 $$$4$$$ 之间的航班,费用为 $$$3$$$,城市 $$$1$$$ 和 $$$1$$$ 之间的航班$$$4$$$ 费用为 $$$3$$$,$$$1$$$ 和 $$$3$$$ 之间的航班费用为 $$$2$$$,最高费用为 $$$3$$$。

城市 $$$3$$$ 和 $$$4$$$ 之间的 Berlaflot 航班费用将为 $$$3$$$,因为 S8 Airlines 往返这些城市的航线的最低费用为 $$$3$$$ — 该航线包括城市 $$$1$$$ 和 $$$3$$$ 之间的航班,费用为 $$$2$$$ 以及城市 $$$1$$$ 和 $$$1$$$ 之间的航班$$$4$$$ 成本为$$$3$$$,最大成本为$$$3$$$。

在第二个测试用例中,S8 航空公司将有以下航班:城市 $$$1$$$ 和 $$$4$$$ 之间的航班,费用为 $$$1$$$;城市 $$$2$$$ 和 $$$3$$$ 之间的费用为 $$$1$$$;城市 $$$2$$$ 和 $$$5$$$ 之间的费用为 $$$2$$$;城市 $$$3$$$ 和 $$$3$$$ 之间的航班。 $$$4$$$ 费用为 $$$1$$$,城市之间 $$$3$$$ 和 $$$5$$$ 费用为 $$$2$$$。