Problem 5106. -- [NEERC2017]Journey from Petersburg to Moscow

5106: [NEERC2017]Journey from Petersburg to Moscow

Time Limit: 300 Sec  Memory Limit: 512 MB
Submit: 11  Solved: 3
[Submit][Status][Web Board]

Description

给定一张n个点,m条边的无向连通图,每条边有边权。
定义一条路径的花费为上面边权最大的k条边的边权和,若这条路径没有k条边,则花费为全部边的边权和。
请找一条1号点到n号点的路径,使得花费最小。

Input

第一行包含三个正整数n,m,k,表示点数、边数以及参数k。
接下来m行,每行三个正整数u,v,w,表示一条连接u和v,边权为w的无向边。
输入数据保证没有重边。
(2<=n<=3000,1<=m<=3000,1<=k<n)
(1<=u,v<=n,u!=v,1<=w<=10^9)

Output

输出一行一个整数,即最小花费。

Sample Input

6 7 2
1 2 6
2 3 1
2 4 3
2 5 5
3 6 10
4 6 9
5 6 8

Sample Output

14

HINT

Source

[Submit][Status]