题目描述

给出一张有 $N$ 个顶点的带权简单无向图，其中点的编号为 $1 \sim N$。保证点 1 不是一个割点（也就是说删除掉点 1 之后，剩下的图仍然连通）。且点 1 到其余 $N-1$ 个点都有连边。

对于每个 $K \in \{1, 2, \ldots, N-1\}$，你需要求出使得点 1 的度数恰好为 $K$ 的生成树的最小权值。

输入格式

• 输入的第一行包含两个整数 $N, M$，分别表示图中点和边的数量。
• 接下来 $M$ 行，每行包含三个整数 $U_i, V_i, W_i$，表示点 $U_i$ 和点 $V_i$ 之间有一条边，权值为 $W_i$。

输出格式

在一行中输出 $N-1$ 个整数：当点 1 的度数恰好分别为 $1, 2, \ldots, N-1$ 时，生成树的最小权值。

输入输出样例 #1

输入 #1

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

输出 #1

5 4 3

说明/提示

数据规模与约定

• $2 \le N \le 100\,000$
• $2N - 3 \le M \le 200\,000$
• $1 \le W_i \le 200\,000$
• $1 \le U_i, V_i \le N$
• 保证图中不存在重边，点 1 不是割点，且其度数等于 $N-1$。

子任务

Hint

本站自制数据哟