P9926 [NFLSPC #6] So How Do You Find the $k$ Smallest Spanning Trees?

Given a connected undirected weighted graph with no self-loops and no multiple edges, find the weights of the first $k$ smallest spanning trees. - The weight of a spanning tree is the sum of the weights of all its edges. - Two spanning trees are different if and only if there exists an edge that is in one spanning tree but not in the other. - If the $i$-th smallest spanning tree does not exist, output $-1$.

The first line contains three integers $n, m, k$. The next $m$ lines each contain three integers $u_i, v_i, w_i$, representing the two endpoints of an undirected edge and its weight.

Output $k$ lines. The $i$-th line contains one integer, representing the weight of the $i$-th smallest spanning tree.

For all testdata, $1\leq n \leq 5\times 10 ^ 4$, $n - 1\leq m\leq 10 ^ 5$, $1\leq k\leq 10 ^ 5$, $1\leq mk\leq 10 ^ 7$, $1\leq u_i, v_i\leq n$, $1\leq w_i\leq 10 ^ 9$. The graph is guaranteed to be connected, with no self-loops and no multiple edges. - Subtask 1 ($10$ points): $m ^ 2k\leq 10 ^ 6$. - Subtask 2 ($20$ points): Each edge belongs to at most one simple cycle. - Subtask 3 ($20$ points): $mk\leq 10 ^ 6$. - Subtask 4 ($50$ points): No special constraints. Source: NFLSPC #6 A by Alex_Wei. Translated by ChatGPT 5