에어 리폼

베를란드는 항공 산업이 발달한 큰 나라이다. 이 나라에는 $n$개의 도시가 있고, 항공사 베를라플롯은 $m$쌍의 도시 사이에 양방향 항공편을 운항한다. $i$번째 항공편은 도시 $a_i$와 $b_i$를 잇고, 양방향 모두 요금이 $c_i$이다. 베를라플롯의 항공편만으로 어떤 도시에서든 다른 도시로 갈 수 있다. 중간에 갈아탈 수도 있다. 여러 항공편으로 이루어진 경로의 비용은 그중 가장 비싼 항공편의 요금과 같다. 정확히는 $t_1$에서 $t_k$까지 $t_2, t_3, \ldots, t_{k-1}$을 거치는 경로의 비용이 $t_1$에서 $t_2$, $t_2$에서 $t_3$, ..., $t_{k-1}$에서 $t_k$까지 항공편 요금의 최댓값이다. 경로에 쓰는 항공편은 모두 베를라플롯이 운항해야 한다.

입력은 여러 테스트 케이스로 이루어진다. 첫 줄에는 테스트 케이스의 수 $t$와 이 테스트가 속한 그룹의 번호 $g$가 주어진다($1 \le t \le 10000$, $0 \le g \le 8$). 각 테스트 케이스의 첫 줄에는 도시의 수 $n$과 베를라플롯 항공편의 수 $m$이 주어진다($4 \le n \le 200000$, $n - 1 \le m \le 200000$, $m \le \frac{(n - 1)(n - 2)}{2}$). 이어서 $m$개의 줄이 주어지며, $i$번째 줄에는 $a_i$, $b_i$, $c_i$가 주어진다($1 \le a_i, b_i \le n$, $1 \le c_i \le 10^9$). 자기 자신을 잇는 항공편은 없고, 같은 도시 쌍을 잇는 항공편은 두 개 이상 없다. 베를라플롯 항공편만으로도, S8 항공편만으로도 어떤 도시에서든 다른 도시로 갈 수 있다. 모든 테스트 케이스에 대해 $n$의 합을 $N$, $m$의 합을 $M$이라 하면 $N, M \le 200000$이다.

각 테스트 케이스마다 $m$개의 정수를 한 줄에 출력한다. $i$번째 정수는 개편 후 베를라플롯의 $i$번째 항공편 요금이다.

첫 번째 테스트 케이스에서 S8 항공은 도시 1과 3, 1과 4, 2와 4 사이에 항공편을 운항한다. 1과 3 사이의 요금은 2이다. 베를라플롯의 가장 저렴한 경로는 1에서 2(요금 1)를 거쳐 2에서 3(요금 2)으로 가는 것이고, 최댓값이 2이기 때문이다. 1과 4 사이의 요금은 3이다. 1, 2, 3, 4를 거치는 경로의 요금이 1, 2, 3이고 최댓값이 3이기 때문이다. 2와 4 사이의 요금은 3이다. 2, 3, 4를 거치는 경로의 최댓값이 3이기 때문이다.

개편 후 도시 1과 2를 잇는 베를라플롯 항공편의 요금은 3이다. S8 항공의 1, 4, 2 경로는 요금이 3과 3이라 최댓값이 3이기 때문이다. 2와 3을 잇는 항공편의 요금은 3이다. S8 항공의 2, 4, 1, 3 경로는 요금이 3, 3, 2이고 최댓값이 3이기 때문이다. 3과 4를 잇는 항공편의 요금은 3이다. S8 항공의 3, 1, 4 경로는 요금이 2와 3이고 최댓값이 3이기 때문이다.

두 번째 테스트 케이스에서 S8 항공은 1과 4 사이에 요금 1, 2와 3 사이에 요금 1, 2와 5 사이에 요금 2, 3과 4 사이에 요금 1, 3과 5 사이에 요금 2의 항공편을 운항한다.