CF125E MST Company

MST（Meaningless State Team）公司再次中标了 Berland 的一项重要国家改革工程。 Berland 有 $n$ 个城市，部分城市之间通过道路相连。每条道路都有其价格。可以沿任意道路双向通行。MST 团队需要选择一组道路进行修缮，使得仅通过修缮后的道路可以从任意城市到达任意其他城市。此外，这组道路中必须恰好包含 $k$ 条“首都道路”（即起点或终点为首都的道路）。首都的编号为 1。 由于预算已获批准，MST 公司希望选择总长度最小的道路集合。

第一行包含三个整数 $n, m, k$（$1 \leq n \leq 5000$，$0 \leq m \leq 10^{5}$，$0 \leq k < 5000$），分别表示国家的城市数、道路数和所需首都道路的数量。接下来 $m$ 行，每行描述一条道路，包含三个整数 $a_i, b_i, w_i$（$1 \leq a_i, b_i \leq n$；$1 \leq w_i \leq 10^{5}$），表示一条连接城市 $a_i$ 和 $b_i$ 的道路，其长度为 $w_i$。 任意一对城市之间最多只有一条道路。不存在起点和终点为同一城市的道路。首都的编号为 1。

第一行输出所选道路的数量。第二行输出所选道路的编号。如果不存在满足条件的方案，输出 $-1$。

由 ChatGPT 4.1 翻译