🟩 Kruskal-2 🧵《最省钱的选边清单》

（输出 MST 的边；多解任选；训练“选边记录与输出”）

题目背景

小猫负责写“施工清单”：不仅要知道最省钱是多少，还要把究竟选了哪些道路打印给加菲老师。

题目描述

给定无向图 $n$ 点 $m$ 边，求一棵 MST，并输出选中的 $n-1$ 条边（按你选边顺序即可）。 如果图不连通输出 -1。

输入格式

第一行 $n,m$。 接下来 $m$ 行：$u,v,w$。

输出格式

• 若无解输出一行 -1
• 否则输出 $n-1$ 行，每行两个整数 u v 表示选中的一条边（可任意一棵 MST）。

数据范围

• $2 \le n \le 2\times 10^5$
• $0 \le m \le 3\times 10^5$
• $1 \le w \le 10^9$
• 允许重边

4 5
1 2 3
2 3 4
3 4 5
1 4 100
2 4 6

1 2
2 3
3 4

解释： 这是其中一种 MST。输出顺序无要求。

4 2
1 2 1
3 4 1

-1