P15408 [NOISG 2026 Prelim] 度数约束生成树（暂无数据）

给出一张有 $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$ 时，生成树的最小权值。

### 数据规模与约定 - $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$。 ### 子任务 |子任务编号|限制条件|分值| |:-:|:-:|:-:| |1|$2 \le N \le 5$|10| |2|$2 \le N \le 1000$|20| |3|$M = 2N - 3$|30| |4|无特殊限制|40|