#描述#
传说中，lost_season是一个XX国的政治经济文化中心，DD无限向往。皇天不负苦心人，终于在一天夜里，DD梦到自己到了XX国，并从国王YY手中得到了一幅XX国的地图。地图上的线路错综复杂，DD看了好半天，才把所有的城市都找出来。
<BR>
<BR>

一共有n座城市，分别编号1~n，DD所在的城市为1，lost_season编号为n。地图上共有m条边，使得城市之间可以相互连通。也就是说，整个图是一个带权无向图。DD每天走过且仅走过一条边，DD想到处走走，但是K天之后DD必须正好在lost_season这个城市（中间走的时候可能已经到过lost_season了）。DD想知道满足这些条件的走法中，走的最短路程是多少？

#格式#
##输入格式##
输入包含多组测试数据，处理到文件结束。
每组数据第一行是三个整数n,m,K(2&lt=n&lt=100,m&lt=10*n,K&lt=10^6)
。接下来是m行，表示m条边。每行三个数A,B,L，表示AB之间有一条长度为L的边(1&lt=A,B&lt=n,1&lt=L&lt=20)。（测试数据中会有重边和自环，并保证有解）

##输出格式##
每组数据输出只有一行，表示K天后DD正好在lost_season的最短路程。

#样例1#
##样例输入1##

2 2 3
1 2 15
1 1 5
3 4 5
3 2 2
3 1 12
3 1 7
1 3 14

##样例输出1##

25
15

#限制#
5000ms
32768KB

#提示#

#来源#
zjut_DD