{"problem":{"name":"[NFLSPC #6] 所以 k 小生成树怎么做？","description":{"content":"给定一张无向带权无自环无重边的连通图，求前 $k$ 小生成树的权值。 - 生成树的权值为其所有边权之和。 - 两棵生成树不同，当且仅当存在一条边在一棵生成树上，但不在另一棵生成树上。 - 若第 $i$ 小生成树不存在，则输出 $-1$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":2097152},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9926"},"statements":[{"statement_type":"Markdown","content":"给定一张无向带权无自环无重边的连通图，求前 $k$ 小生成树的权值。\n\n- 生成树的权值为其所有边权之和。\n- 两棵生成树不同，当且仅当存在一条边在一棵生成树上，但不在另一棵生成树上。\n- 若第 $i$ 小生成树不存在，则输出 $-1$。\n\n## Input\n\n第一行三个整数 $n, m, k$。\n\n接下来 $m$ 行，每行三个整数 $u_i, v_i, w_i$，分别表示无向边的两端及其权值。\n\n## Output\n\n输出 $k$ 行，第 $i$ 行一个整数表示第 $i$ 小生成树的权值。\n\n[samples]\n\n## Note\n\n对于所有数据，$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$。保证图连通，无自环，无重边。\n\n- 子任务 1（$10$ 分）：$m ^ 2k\\leq 10 ^ 6$。\n- 子任务 2（$20$ 分）：保证每条边至多属于一个简单环。\n- 子任务 3（$20$ 分）：$mk\\leq 10 ^ 6$。\n- 子任务 4（$50$ 分）：无特殊限制。\n\nSource：NFLSPC #6 A by Alex_Wei","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9926","tags":["O2优化"],"sample_group":[["4 6 17\n1 2 4\n1 3 7\n1 4 6\n2 3 8\n2 4 5\n3 4 7\n","16\n16\n17\n17\n17\n18\n18\n18\n18\n19\n19\n19\n20\n21\n21\n22\n-1\n"]],"created_at":"2026-03-03 11:09:25"}}