“你是我心中最美的云彩...."，这不是大妈的广场舞，而是大红的闹钟，然而大红由于昨晚在优衣库玩得太疯，导致今天居然没被这铃声闹醒！
当大红睡眼惺忪地醒来后，发现距离网络赛开始还有不到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可能有自环以及重边
其中大红宿舍在1号节点，实验室在n号节点。
保证从宿舍到实验室至少存在一条路。

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