Description

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

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

Input

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

Output

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

Sample

Input

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

Output

25
15

Source: zjut_DD