Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:9 MB
统计

绿化工程终于完成,整个园区生机勃勃。但是,很不幸的是,在绿化过程中,工人们和进出的车辆将铺设好的电话线全部破坏了。Neyc的领导很生气,问题很严重。为了保住面子,工程队负责人,希望尽快恢复园区的电信,他把这个任务交给了你。已知,园区周围分布n$(1\le n\le 1000)$根按1…n排列的电话线杆,电话线杆之间可以拉电话线。第i对电话线杆的两个端点分别为Ai,Ri,它们间的距离为Li$(1\le li\le 1000000)$。数据中保证每对最多只出现一次。编号为1的电话线杆已经接入了全国的电话网络,整个园区的电话线全部连到了编号为N的电话线杆上。也就是说,你的任务仅仅是找一条将1号和N号电话线杆连起来的路径,其余的电话线杆并不一定要连入电话网络。绿化工程的负责人与电信公司协商后,电信公司决定免费为园区连接K$(0\le k\lt n)$对由你指定的电话线杆。对于此外的那些电话线,就必需为它们付费,总费用等于其中最长的电话线长度(每根电话线仅连接一对电话线杆),其它长度不付费。如果需要连接的电话线杆不超过K对,那么总支出为0。现在,你就要设计一个费用最少的方案。最后,计算出将电话线引到园区最少需要花多少钱?
【输入格式】
输入文件的第一行包含三个用空格隔开的整数:N ,P和K。
第二行到第P+1行:每行分别都为三个用空格隔开的整数:Ai Bi和Li。
【输出格式】
输出文件仅包含一个整数,表示在这项工程上的最小支出。如果任务不可能完成,则输出-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