鸡尾酒在去西湖的路上遇到了两个可爱的妹子，妹子邀请他一起逛西湖。但是西湖周边的景点太多了，还有许多道路让人眼花缭乱。初始鸡尾酒和妹子在第1个景点，妹子的目标是第N个景点。其中一些景点间有双向道路连接，也有一些景点间没有路，经过每条路都要消耗一定的时间。鸡尾酒不在意中间这些景点，他只想最快的领妹子到第N的景点。他带的钱可以带他和妹子乘坐k次观光车，观光车可以使他从某一个景点到另一个景点的时间消耗变为1（前提是两个景点间有直达的道路）
求鸡尾酒从点1走到点N的最短时间。
输入第一行给两个正整数N，M, K(1<=N,M<=1e5,1<=k<=5)代表有N个点，M条路径，可以乘坐k次观光车
接下来M行，每行给出三个整数a b c，代表a b两点间有一条路，需要时间c才能通过。(1<=a,b <= N, 1<=c <= 1e9)
输出一行一个整数表示答案