网络赛前10奖励计蒜客的本子或鼠标垫(外校也可以来现场领取)

问题 1078. -- 大红要迟到了!

1078: 大红要迟到了!

时间限制: 1 Sec  内存限制: 128 MB
提交: 41  解决: 14
[提交][状态][讨论版]

题目描述

“你是我心中最美的云彩....",这不是大妈的广场舞,而是大红的闹钟,然而大红由于昨晚在优衣库玩得太疯,导致今天居然没被这铃声闹醒!
当大红睡眼惺忪地醒来后,发现距离网络赛开始还有不到5分钟了!
大红心想,跑过去实验室肯定来不及了,只好发动一下超能力。
大红的超能力是可以瞬间通过一条路,也就是说从一头瞬间移动到另一头,然而由于某种原因,大红最多只能发动K次,不然就会被大家发现,就会被上交给国家。
那么大红想问你最快要多长时间到达实验室?

输入

多组数据,每组数据首先是三个整数N,M,K,表示校园道路的节点数,校园道路数,还有大红能发动超能力的最大次数。
(2<=N<=1000,N-1<=M<=10000,0<=K<=10)
接下来是M行,每行是三个数字u,v,w,表示在节点u和节点v中有一条需要大红跑w分钟的路,道路都是没有方向限制的。
(1<=u,v<=N,0<w<=1000)
可能有自环以及重边
其中大红宿舍在1号节点,实验室在n号节点。
保证从宿舍到实验室至少存在一条路。

输出

对于每组数据,输出一个整数,表示大红在超能力的帮助下最少要多少时间到达实验室。

样例输入

4 4 0
1 2 2
2 4 3
1 3 1
3 4 4
4 4 1
1 2 2
2 4 3
1 3 1
3 4 4

样例输出

5
1

提示

来源

[提交][状态][讨论版]