Description

伯兰德是一个拥有发达航空网络的大国。全国共有 $n$ 个城市，这些城市一直由 Berlaflot 航空公司运营。该公司在 $m$ 对城市间运营双向航班，第 $i$ 条航线连接城市 $a_i$ 和 $b_i$，票价为 $c_i$，双向价格相同。

已知通过 Berlaflot 的航班，可以从任意城市到达任意其他城市（可能需要中转）。对于一条由多段航班组成的路径，其总费用等于其中最贵一段的费用。更正式地说，从城市 $t_1$ 到 $t_k$（中转 $k-2$ 次），路径费用为 $t_1$ 到 $t_2$，$t_2$ 到 $t_3$，……，$t_{k-1}$ 到 $t_k$ 这些航班中费用的最大值。当然，所有航段都必须由 Berlaflot 执飞。

最近，S8 Airlines 新进入了伯兰德市场。S8 Airlines 在所有未被 Berlaflot 连接的城市对之间开通了双向航班。也就是说，任意一对城市之间，要么有 Berlaflot 的航班，要么有 S8 Airlines 的航班。

S8 Airlines 的航班费用如下：对于通过 S8 Airlines 连接的城市 $x$ 和 $y$，其票价等于 Berlaflot 网络下 $x$ 和 $y$ 之间所有路径中费用最小的那一条（即路径上的最大航段费用最小）。

已知通过 S8 Airlines 的航班，也可以在所有城市之间互达，且路径费用定义同上，也是路径上最大航段费用。

由于 S8 Airlines 的竞争，Berlaflot 决定进行航空改革，调整自家航班票价：对于 Berlaflot 的第 $i$ 条航班（连接 $a_i$ 和 $b_i$），新票价应等于 S8 Airlines 网络下 $a_i$ 和 $b_i$ 之间的最小路径费用。请帮 Berlaflot 计算每条航班改革后的新票价。

Input Format

每组测试包含多组数据。第一行包含两个整数 $t$ 和 $g$（$1 \le t \le 10\,000$，$0 \le g \le 8$），分别表示测试组数和当前测试组编号。接下来是 $t$ 组测试数据。

每组测试的第一行包含两个整数 $n$ 和 $m$（$4 \le n \le 200\,000$，$n-1 \le m \le 200\,000$，$m \le \frac{(n-1)(n-2)}{2}$），分别表示城市数量和 Berlaflot 航班数量。

接下来的 $m$ 行，每行三个整数 $a_i, b_i, c_i$（$1 \le a_i, b_i \le n$，$1 \le c_i \le 10^9$），表示第 $i$ 条航班连接的城市和票价。

保证没有航班连接同一个城市，也没有两条航班连接同一对城市。保证 Berlaflot 和 S8 Airlines 的航班网络都连通。

记所有测试数据中 $n$ 的总和为 $N$，$m$ 的总和为 $M$。保证 $N, M \le 200\,000$。

Output Format

对于每组测试数据，输出 $m$ 个整数，第 $i$ 个为第 $i$ 条 Berlaflot 航班改革后的新票价，按输入顺序输出，空格分隔。

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

Hint

说明

在第一个测试样例中，S8 Airlines 会在以下城市对之间开通航班：（1,3）、（1,4）、（2,4）。

城市 1 和 3 之间的 S8 航班费用为 2，因为 Berlaflot 网络下最小路径费用为 2（1-2 票价 1，2-3 票价 2，最大为 2）。

城市 1 和 4 之间的 S8 航班费用为 3，因为 Berlaflot 网络下最小路径费用为 3（1-2 票价 1，2-3 票价 2，3-4 票价 3，最大为 3）。

城市 2 和 4 之间的 S8 航班费用为 3，因为 Berlaflot 网络下最小路径费用为 3（2-3 票价 2，3-4 票价 3，最大为 3）。

航空改革后，Berlaflot 的航线 1-2 的票价变为 3，因为 S8 Airlines 网络下 1 和 2 之间最小路径费用为 3（1-4 票价 3，2-4 票价 3，最大为 3）。

航线 2-3 的票价也变为 3，因为 S8 网络下 2 和 3 的最小路径费用为 3（2-4 票价 3，1-4 票价 3，1-3 票价 2，最大为 3）。

航线 3-4 的票价也变为 3，因为 S8 网络下 3 和 4 的最小路径费用为 3（1-3 票价 2，1-4 票价 3，最大为 3）。

第二个测试样例中，S8 Airlines 会在城市对（1,4）、（2,3）、（2,5）、（3,4）、（3,5）之间开通航班，票价分别为 1、1、2、1、2。

评分说明

本题测试数据分为 8 组。只有通过某组所有测试点，且通过所有必需的前置组，才能获得该组分数。离线评测表示该组的评测结果将在比赛结束后公布。有些分组不要求通过样例测试点。