Air Reform

Berland is a large country with developed airlines. It has $n$ cities, and the airline Berlaflot operates bidirectional flights between $m$ pairs of cities. The $i$-th flight connects cities $a_i$ and $b_i$ and costs $c_i$ in both directions. Berlaflot flights can be used to get from any city to any other, possibly with transfers. The cost of a route made of several consecutive flights is the maximum cost among those flights. More formally, the cost of a route from $t_1$ to $t_k$ through the cities $t_2, t_3, \ldots, t_{k-1}$ is the maximum cost of the flights from $t_1$ to $t_2$, from $t_2$ to $t_3$, and so on until the flight from $t_{k-1}$ to $t_k$. All flights on the route must be operated by Berlaflot.

Each test consists of multiple test cases. The first line contains two integers $t$ and $g$ ($1 \le t \le 10000$, $0 \le g \le 8$), the number of test cases and the number of the group this test belongs to. Each test case starts with a line containing $n$ and $m$ ($4 \le n \le 200000$, $n - 1 \le m \le 200000$, $m \le \frac{(n - 1)(n - 2)}{2}$), the number of cities and the number of Berlaflot flights. Then $m$ lines follow. The $i$-th line contains $a_i$, $b_i$, and $c_i$ ($1 \le a_i, b_i \le n$, $1 \le c_i \le 10^9$). No flight connects a city to itself, and no two flights connect the same pair of cities. Berlaflot flights can reach any city from any other city, and S8 Airlines flights can too. Let $N$ be the sum of $n$ and $M$ be the sum of $m$ over all test cases. Then $N, M \le 200000$.

For each test case, print $m$ integers on a single line. The $i$-th integer is the new price of the $i$-th Berlaflot flight.

In the first test case, S8 Airlines provides flights between cities 1 and 3, 1 and 4, and 2 and 4. The cost of the flight between 1 and 3 is 2, because the cheapest Berlaflot route goes from 1 to 2 (cost 1) and then from 2 to 3 (cost 2), and its maximum is 2. The cost between 1 and 4 is 3, because the route 1 to 2 to 3 to 4 has costs 1, 2, 3 and maximum 3. The cost between 2 and 4 is 3, because the route 2 to 3 to 4 has maximum 3.

After the reform, the cost of the Berlaflot flight between 1 and 2 is 3, because the S8 route 1 to 4 to 2 has costs 3 and 3, so its maximum is 3. The cost of the flight between 2 and 3 is 3, because the S8 route 2 to 4 to 1 to 3 has costs 3, 3, 2, and its maximum is 3. The cost of the flight between 3 and 4 is 3, because the S8 route 3 to 1 to 4 has costs 2 and 3, and its maximum is 3.

In the second test case, S8 Airlines has flights between 1 and 4 costing 1, 2 and 3 costing 1, 2 and 5 costing 2, 3 and 4 costing 1, and 3 and 5 costing 2.