CF1648E.Air Reform

Berland is a large country with developed airlines. In total, there are $n$ cities in the country that are historically served by the Berlaflot airline. The airline operates bi-directional flights between $m$ pairs of cities, $i$-th of them connects cities with numbers $a_i$ and $b_i$ and has a price $c_i$ for a flight in both directions.

It is known that Berlaflot flights can be used to get from any city to any other (possibly with transfers), and the cost of any route that consists of several consequent flights is equal to the cost of the most expensive of them. More formally, the cost of the route from a city $t_1$ to a city $t_k$ with $(k-2)$ transfers using cities $t_2,\ t_3,\ t_4,\ \ldots,\ t_{k - 1}$ is equal to the maximum cost of flights from $t_1$ to $t_2$, from $t_2$ to $t_3$, from $t_3$ to $t_4$ and so on until the flight from $t_{k - 1}$ to $t_k$. Of course, all these flights must be operated by Berlaflot.

A new airline, S8 Airlines, has recently started operating in Berland. This airline provides bi-directional flights between all pairs of cities that are not connected by Berlaflot direct flights. Thus, between each pair of cities there is a flight of either Berlaflot or S8 Airlines.

The cost of S8 Airlines flights is calculated as follows: for each pair of cities $x$ and $y$ that is connected by a S8 Airlines flight, the cost of this flight is equal to the minimum cost of the route between the cities $x$ and $y$ at Berlaflot according to the pricing described earlier.

It is known that with the help of S8 Airlines flights you can get from any city to any other with possible transfers, and, similarly to Berlaflot, the cost of a route between any two cities that consists of several S8 Airlines flights is equal to the cost of the most expensive flight.

Due to the increased competition with S8 Airlines, Berlaflot decided to introduce an air reform and change the costs of its flights. Namely, for the $i$-th of its flight between the cities $a_i$ and $b_i$, Berlaflot wants to make the cost of this flight equal to the minimum cost of the route between the cities $a_i$ and $b_i$ at S8 Airlines. Help Berlaflot managers calculate new flight costs.

贝尔兰是一个拥有发达航空业的大国。全国共有 $n$ 座城市，历史上均由贝尔弗洛特（Berlaflot）航空公司提供服务。该航空公司运营着 $m$ 条双向航线，其中第 $i$ 条航线连接编号为 $a_i$ 和 $b_i$ 的两座城市，往返票价均为 $c_i$。

已知：利用贝尔弗洛特的航班，可以从任意一座城市抵达任意另一座城市（允许中转），且由若干连续航班构成的整条路线的总费用，等于其中最贵的一段航班的费用。更准确地说，若从城市 $t_1$ 出发，经 $(k-2)$ 次中转，依次经过城市 $t_2,\ t_3,\ t_4,\ \ldots,\ t_{k - 1}$，最终抵达城市 $t_k$，则该路线的费用等于以下各段航班费用的最大值：$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 航空公司的激烈竞争，贝尔弗洛特决定实施航空改革，调整其航线票价。具体而言，对于其第 $i$ 条连接城市 $a_i$ 与 $b_i$ 的航线，贝尔弗洛特希望将其票价调整为：S8 航空公司网络中城市 $a_i$ 与 $b_i$ 之间的最小路线费用。请帮助贝尔弗洛特的管理人员计算出各项航线的新票价。

Each test consists of multiple test cases. The first line contains one integer $t$ ($1 \le t \le 10\,000$) — the amount of test cases.

The first line of each test case contains two integers $n$ and $m$ ($4 \le n \le 200\,000$, $n - 1 \le m \le 200\,000$, $m \le \frac{(n - 1) (n - 2)}{2}$) — the amount of cities in Berland and the amount of Berlaflot flights.

The next $m$ lines contain the description of Berlaflot flights. The $i$-th line contains three integers $a_i$, $b_i$ and $c_i$ ($1 \le a_i, b_i \le n$, $1 \le c_i \le 10^9$) — the numbers of cities that are connected with $i$-th Berlaflot flight and the price of $i$-th Berlaflot flight.

It is guaranteed that no flight connects a city with itself, no two flights connect the same pair of cities. It is guaranteed that by using Berlaflot flights it is possible to get from any city to any other and by using S8 Airlines flights it is possible to get from any city to any other.

Let $N$ be the sum of $n$ over all test cases and $M$ be the sum of $m$ over all test cases. It is guaranteed that $N, M \le 200\,000$.

每个测试包含多个测试用例。第一行包含一个整数 $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$ 个 Berlaflot 航班所连接的两个城镇编号及其票价。

保证不存在连接某城镇与其自身的航班，也不存在两个航班连接完全相同的两个城镇。同时保证：仅使用 Berlaflot 航班可从任意城镇到达任意其他城镇；仅使用 S8 Airlines 航班也可从任意城镇到达任意其他城镇。

令 $N$ 表示所有测试用例中 $n$ 的总和，$M$ 表示所有测试用例中 $m$ 的总和。保证 $N, M \le 200\,000$。

For each test case you should print $m$ integers in a single line, $i$-th of them should be the price of $i$-th Berlaflot flight after the air reform.

对于每个测试用例，您应在一行中输出 $m$ 个整数，其中第 $i$ 个整数应为航空改革后第 $i$ 趟贝尔拉弗洛特（Berlaflot）航班的价格。

In the first test case S8 Airlines will provide flights between these pairs of cities: $(1, 3)$, $(1, 4)$ and $(2, 4)$.

The cost of a flight between cities $1$ and $3$ will be equal to $2$, since the minimum cost of the Berlaflot route is $2$ — the route consists of a flight between cities $1$ and $2$ costing $1$ and a flight between cities $2$ and $3$ costing $2$, the maximum cost is $2$.

The cost of a flight between cities $1$ and $4$ will be $3$, since the minimum cost of the Berlaflot route is $3$ — the route consists of a flight between cities $1$ and $2$ costing $1$, a flight between cities $2$ and $3$ costing $2$ and a flight between cities $3$ and $4$ costing $3$, the maximum cost is $3$.

The cost of a flight between cities $2$ and $4$ will be $3$, since the minimum cost of the Berlaflot route is $3$ — the route consists of a flight between cities $2$ and $3$ costing $2$ and a flight between cities $3$ and $4$ costing $3$, the maximum cost is $3$.

After the air reform, the cost of the Berlaflot flight between cities $1$ and $2$ will be $3$, since the minimum cost of the S8 Airlines route between these cities is $3$ — the route consists of a flight between cities $1$ and $4$ costing $3$ and a flight between cities $2$ and $4$ costing $3$, the maximum cost is $3$.

The cost of the Berlaflot flight between cities $2$ and $3$ will be $3$, since the minimum cost of the S8 Airlines route between these cities is $3$ — the route consists of a flight between cities $2$ and $4$ costing $3$, a flight between cities $1$ and $4$ costing $3$ and a flight between $1$ and $3$ costing $2$, the maximum cost is $3$.

The cost of the Berlaflot flight between cities $3$ and $4$ will be $3$, since the minimum cost of the S8 Airlines route between these cities is $3$ — the route consists of a flight between cities $1$ and $3$ costing $2$ and a flight between cities $1$ and $4$ costing $3$, the maximum cost is $3$.

In the second test case S8 Airlines will have the following flights: between cities $1$ and $4$ costing $1$, between cities $2$ and $3$ costing $1$, between cities $2$ and $5$ costing $2$, between cities $3$ and $4$ costing $1$ and between cities $3$ and $5$ costing $2$.

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

城市 $1$ 与 $3$ 之间航班的费用为 $2$，因为 Berlaflot 航线的最小费用为 $2$ —— 该航线由一条城市 $1$ 与 $2$ 之间费用为 $1$ 的航班和一条城市 $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$。

航空改革后，Berlaflot 公司在城市 $1$ 与 $2$ 之间的航班费用将变为 $3$，因为 S8 航空公司在这些城市之间的航线的最小费用为 $3$ —— 该航线由一条城市 $1$ 与 $4$ 之间费用为 $3$ 的航班和一条城市 $2$ 与 $4$ 之间费用为 $3$ 的航班组成，其中最大费用为 $3$。

Berlaflot 公司在城市 $2$ 与 $3$ 之间的航班费用将变为 $3$，因为 S8 航空公司在这些城市之间的航线的最小费用为 $3$ —— 该航线由一条城市 $2$ 与 $4$ 之间费用为 $3$ 的航班、一条城市 $1$ 与 $4$ 之间费用为 $3$ 的航班以及一条城市 $1$ 与 $3$ 之间费用为 $2$ 的航班组成，其中最大费用为 $3$。

Berlaflot 公司在城市 $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$。