1196: 架设电话线

题目

题目描述

FarmerJohn打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。FJ的农场周围分布着$N$根按$1\cdots N$顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共$P$对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。

第$i$对电话线杆的两个端点分别为$A_i,B_i$，它们间的距离为$L_i$。数据中保证每对$(A_i,B_i)$最多只出现一次。编号为$1$的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为$N$的电话线杆上。也就是说，FJ的任务仅仅是找一条将$1$号和$N$号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。经过谈判，电信公司最终同意免费为FJ连结$K$对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过$K$对，那么FJ的总支出为$0$。请你计算一下，FJ最少需要在电话线上花多少钱。

输入格式

第一行: 三个用空格隔开的整数：$N,P,K$

第$2\cdots P+1$行: 第$i+1$行为三个用空格隔开的整数：$A_i,B_i,L_i$

输出格式

输出一行一个整数，表示最少花费。

如果不可能完成，输出$-1$。

样例输入

5 7 1

1 2 5

3 1 4

2 4 8

3 2 3

5 2 9

3 4 7

4 5 6

样例输出

4

提示

FJ选择如下的连结方案：$1->3；3->2；2->5$，这三对电话线杆间需要的电话线的长度分别为$4、3、9$。FJ让电信公司提供那条长度为$9$的电话线，于是，他所需要购买的电话线的最大长度为$4$。

数据范围

对于 $100\%$的数据，$1\le N \le 1000,1 \le P \le 10000,1\le L_i \le 1000000,0\le K< N$。

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！