Bobo 有一个包含 $n$ 个顶点和 $m$ 条边的连通无向简单图。 顶点编号为 $1, 2, \dots, n$，第 $i$ 条边的权重为 $c_i$。

对于每个整数 $k \in [2, n]$，Bobo 希望选择一个边子集，使得顶点 $1, 2, \dots, k$ 相互连通。 满足条件的边子集权重之和的最小值为 $f(k)$。

请计算 $f(2), f(3), \dots, f(n)$ 的值。

输入格式

输入包含多组测试数据，以文件结束符（EOF）终止。

每组测试数据的第一行包含两个整数 $n$ 和 $m$。

接下来的 $m$ 行中，第 $i$ 行包含 3 个整数 $a_i, b_i$ 和 $c_i$，表示连接顶点 $a_i$ 和 $b_i$ 且权重为 $c_i$ 的边。

输出格式

对于每组测试数据，输出 $(n - 1)$ 个整数，分别表示 $f(2), f(3), \dots, f(n)$。

样例

样例输入 1

4 3
1 4 1
2 4 1
3 4 1
4 6
1 2 1
1 3 2
1 4 3
2 3 4
2 4 5
3 4 6

样例输出 1

2
3
3
1
3
6

数据范围

• $2 \leq n \leq 26$
• $n - 1 \leq m \leq \frac{n(n - 1)}{2}$
• $1 \leq a_i, b_i \leq n$
• $1 \leq c_i \leq 1000$
• 测试数据组数不超过 $100$。
• $n > 8$ 的测试数据组数不超过 $5$。