3389: 小 W 拼图
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
小 W 和小 M 一起玩拼图游戏啦~
小 M 给小 M 一张 N 个点的图，有 M 条可选无向边，每条边有一个甜蜜值，小 W 要选 K条边，使得任意两点间最多有一条路径，并且选择的 K条边甜蜜值之和最大。
输入
第一行三个正整数 N,M,K。
接下来 M 行，每行三个正整数 A,B,C，表示 A、B 两点间有一条甜蜜值为 C 的无向边。
输出
一行输出最大甜蜜值之和。
样例输入 复制
5 4 3
1 2 10
1 3 9
2 3 7
4 5 3样例输出 复制
22提示
对于 20%的数据：K=1
对于 60%的数据：N,M<=1000，原图不含环
对于 100%的数据：N,M<=100000