2443: 阿Q的密室
内存限制：128 MB
时间限制：4.000 S
评测方式：文本比较
命题人：
提交：50
解决：11
题目描述
蛋大有n个密室，从1到n标号，之间由m条错综复杂的双向道路相连，但初始时都是没有开启的。阿Q希望开启密室中的某些道路，把n个密室分成k组，使得每组中的密室都可以互相到达。 由于启用道路的代价和道路的长度成正比。显然没有人会介意省钱，她自然希望启用的道路长度尽量短。
输入
第一行，三个整数n,m,k，表示密室数，道路数，组数； 接下来m行，每行三个整数x,y,z，表示x与y由长为z的道路连接；
输出
一行一个整数，表示启用道路的最短长度，无解输出-1。
样例输入 复制
3 1 2
1 2 1 样例输出 复制
1提示
对于30%的数据 n<=5000
对于100%的数据 n,m<=1000000，k<=n，z<=10^9