P15408 [NOISG 2026 Prelim] Degree-Constrained Spanning Tree (No testdata yet).

You are given a weighted simple undirected graph with $N$ vertices, numbered $1 \sim N$. It is guaranteed that vertex $1$ is not an articulation point (that is, after deleting vertex $1$, the remaining graph is still connected). Also, vertex $1$ has an edge to each of the other $N-1$ vertices. For each $K \in \{1, 2, \ldots, N-1\}$, you need to find the minimum total weight of a spanning tree in which the degree of vertex $1$ is exactly $K$.

- The first line contains two integers $N, M$, representing the number of vertices and edges in the graph. - The next $M$ lines each contain three integers $U_i, V_i, W_i$, indicating that there is an edge between vertex $U_i$ and vertex $V_i$ with weight $W_i$.

Output $N-1$ integers in one line: the minimum total weight of a spanning tree when the degree of vertex $1$ is exactly $1, 2, \ldots, N-1$, respectively.

### Constraints - $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$. - It is guaranteed that there are no multiple edges in the graph, vertex $1$ is not an articulation point, and its degree is $N-1$. ### Subtasks |Subtask ID|Constraints|Score| |:-:|:-:|:-:| |1|$2 \le N \le 5$|10| |2|$2 \le N \le 1000$|20| |3|$M = 2N - 3$|30| |4|No additional constraints.|40| Translated by ChatGPT 5