Problem Description

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$.

Input Format

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 Format

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

4 6 17
1 2 4
1 3 7
1 4 6
2 3 8
2 4 5
3 4 7

16
16
17
17
17
18
18
18
18
19
19
19
20
21
21
22
-1

Hint

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