← 返回题目列表

Codeforces · 125/E

E. MST公司

中文机器翻译题面 查看原题

MST(无意义的国家团队)公司赢得了伯兰一项重要国家改革的另一项招标。

Berland有n个城市,其中一些城市之间有道路相连。每条路都有它的价格。一个人可以沿着任何道路向任何方向移动。 MST团队应该对一些道路进行修复工作,这样人们只需沿着修复后的道路就可以从任何一个城市到达任何另一个城市。此外,该集合应恰好包含 k 条首都道路(即在首都开始或结束的道路)。首都的数量是1。

由于预算已经获得批准,MST 公司将通过找到道路长度最小的集合来获利。

输入

第一输入行包含三个整数 n、m、k (1 ≤ n ≤ 5000;0 ≤ m ≤ 105;0 ≤ k < 5000),其中 n 是该国城市的数量,m 是该国道路的数量,k 是所需集合中首都道路的数量。然后 m 行枚举有问题的道路。每条道路由三个数字 ai、bi、wi 指定(1 ≤ ai、bi ≤ n;1 ≤ w ≤ 105),其中 ai、bi 是一条道路连接的城市数量,wi 是其长度。

每对城市之间不存在超过一条道路。没有一条道路在一个城市内开始和结束。首都编号为1。

输出

在第一行中打印所需组中的道路数量。第二行应包含所查找集合中包含的道路数量。如果查找的集合不存在,则打印-1。

示例

输入 #1

4 5 2
1 2 1
2 3 1
3 4 1
1 3 3
1 4 2

输出 #1

3
1 5 2