AT_arc225_c [ARC225C] K Spanning Tree

给定一个简单连通无向图 $G$ ，包含 $N$ 个顶点和 $M$ 条边。第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，权重为 $c_i$。每条边的权重要么是 $0$，要么是 $1$。 给定一个非负整数 $K$。请判断是否存在一棵 $G$ 的生成树，使得生成树所包含的边的权值之和恰好等于 $K$，如果存在，输出一种满足要求的生成树。 共给出 $T$ 组测试数据；请依次解决每组数据。

输入按以下格式给出： > $T$ > $\text{case}_1$ > $\text{case}_2$ > $\vdots$ > $\text{case}_T$ 每组数据格式如下： > $N$ $M$ $K$ > $a_1$ $b_1$ $c_1$ > $a_2$ $b_2$ $c_2$ > $\vdots$ > $a_M$ $b_M$ $c_M$

输出 $T$ 行，第 $i$ 行为该测试用例的答案。 如果不存在满足条件的生成树，输出 `-1`。 否则，设 $x_1, x_2, \cdots, x_{N-1}$ 是该生成树所用的边的编号，请以如下格式输出： > $x_1$ $x_2$ $\cdots$ $x_{N-1}$ $ x_1, x_2, \cdots, x_{N-1}$ 的顺序任意。这里的编号是指在每组输入中的边的编号。如果有多种选择，输出任意一种都可。

### 样例解释 1 对于第一组数据，选择第 $1,4,5$ 条边组成的图构成一棵生成树，且这些边的权值和为 $2$，满足条件。 类似地，输出如 `2 4 5` 或 `4 1 5` 也是可行的。 对于第二组数据，该图任意生成树边权之和都无法为 $1$。 ### 数据范围 - $1 \le T \le 10^5$ - $2 \le N \le 2\times 10^5$ - $N-1 \le M \le \min\left(\frac{N(N-1)}{2}, 2\times 10^5\right)$ - $0 \le K \le N-1$ - $1 \le a_i, b_i \le N$ - $c_i=0$ 或 $c_i=1$ - 图 $G$ 保证简单且连通。 - 所有测试用例的 $N$ 之和不超过 $2\times 10^5$。 - 所有测试用例的 $M$ 之和不超过 $2\times 10^5$。 - 所有输入均为整数。 由 ChatGPT 5 翻译