题目背景

CF1648E

题目描述

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 the city $t_1$ to the city $t_k$ with $(k-2)$ transfers in 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 Airline.

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 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 the route between any two cities that consists of several S8 Airlines flights is equal to the cost of the most expensive flight.

Due to 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.

输入格式

Each test consists of multiple test cases. The first line contains two integers $t$ and $g$ ($1 \le t \le 10\,000$, $0 \le g \le 8$) --- the amount of test cases and the number of the group which this test belongs to. Description of the test cases follows.

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. $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 2 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$.

输出格式

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.

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

提示

Note

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.

Scoring

Tests for this problem are divided into 8 groups. For each of the groups you earn points only if your solution passes all tests in this group and all tests in required groups. Note that passing sample tests is not required for some groups. $\textbf{Offline evaluation}$ means that your submission will be evaluated on the tests of the group only after the end of the contest.

Group	Points	Additional constraints	<		Required groups	Comment
		$n$	$N$	$c_i$
0		--		--	--	Sample tests.
1	11	$n \le 10$	$N \le 10\,000$		0
2	10	$n \le 100$			0, 1
3	11	$n \le 1000$		$c_i \le 2$	--
4	12			--	0, 1, 2
5		--			--	In all test cases $m = n - 1$
6	17			$c_i \le 2$	3
7	10			$c_i \le 10$	3, 6
8	17			--	0 -- 7	Offline-evaluation.