Air Reform
Contest: Codeforces Round 775 (Div. 1, based on Moscow Open Olympiad in Informatics)
Difficulty rating: 3200
Tags: data structures, dfs and similar, divide and conquer, dsu, graphs, implementation, trees

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

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

Example input:
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

Example output:
3 3 3 
1 1 1 2 2 
4 4 5 3 4 4

Editorial:
The formal statement of this problem is that we have a weighted graph, for which we build it's complement, where the weight of an edge between $$$A$$$ and $$$B$$$ equals to minimal maximum on path from $$$A$$$ to $$$B$$$ in initial graph. The same way we calculate edge weights of initial graph, and we have to output them.
We can notice, that the path where maximum wight is minimal goes directly through the minumum spanning tree. That means that in order to get the final edges weights we need to calculate the minimum spanning tree on the graph complement and to get the final weights of initial edges we need to get the maximum on the tree path, which we can do in $$$O(m \log n)$$$ time with binary jumping pointers.
In order to build the minimum spanning tree of graph complement, we will do something like Kruskal algorithm. We will sort the edges of initial graph by their weights and store sets of connected vertices by edges of weights less than last added. The same way we will store the sets of connected vertices in graph complement by edges of weights less than last added. These complement components will form subsets of initial components.
While adding a new edge, some connected components of initial graph can be merged. That means that some complement components can be merged. We can merge only those complement components, that are subsets of different initial components that became merged after adding an edge. These complement components become merged only if there exists some edge between two vertices of complement components in complement graph. In other words, between some pair of vertices in different complement components there is no edge in initial graph.
So when two initial components $$$S$$$ and $$$T$$$ become merged, we can iterate over all pair of complement components, such that first one is subset of $$$S$$$ and second one is subset of $$$T$$$. For each two vertices in them we should check that there is an edge between them in initial graph. Only in this case we can not merge these two complement components. For each of this unsuccessful attempt of merging two complement components, we do as much iterations, as there are edges between them in initial graph. So the total number of iterations in unsuccessful merges is $$$O(m)$$$. And for successful merges the complement components are merged and a new edge is added to complement minimum spanning tree. So the total number of successful merges is $$$O(n)$$$ and the total time if $$$O(m \log m)$$$ for edges sorting and $$$O(m)$$$ for complement MST build. After that we can find weights of initial edges in $$$O(m \log n)$$$ time.