题目描述

给定一张无向带权无自环无重边的连通图，求前 $k$ 小生成树的权值。

• 生成树的权值为其所有边权之和。
• 两棵生成树不同，当且仅当存在一条边在一棵生成树上，但不在另一棵生成树上。
• 若第 $i$ 小生成树不存在，则输出 $-1$。

输入格式

第一行三个整数 $n, m, k$。

接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$，分别表示无向边的两端及其权值。

输出格式

输出 $k$ 行，第 $i$ 行一个整数表示第 $i$ 小生成树的权值。

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

提示

对于所有数据，$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$。保证图连通，无自环，无重边。

• 子任务 1（$10$ 分）：$m ^ 2k\leq 10 ^ 6$。
• 子任务 2（$20$ 分）：保证每条边至多属于一个简单环。
• 子任务 3（$20$ 分）：$mk\leq 10 ^ 6$。
• 子任务 4（$50$ 分）：无特殊限制。

Source：NFLSPC #6 A by Alex_Wei