题目描述

每天,农夫$\red{John}$需要经过一些道路去检查牛棚$\red{N}$里面的牛.

农场上有$\red{M(1<=M<=50,000)}$条双向泥土道路,编号为$\red{1..M. }$道路$\red{i}$连接牛棚$\red{P1_i}$和$\red{P2_i (1 <= P1_i <= N}$; $\red{1 <= P2_i<= N). John}$需要$\red{T_i (1 <= T_i <= 1,000,000)}$时间单位用道路$\red{i}$从$\red{P1_i}$走到$\red{P2_i}$或者从$\red{P2_i }$走到$\red{P１}$$\red{_i }$他想更新一些路经来减少每天花在路上的时间.

具体地说,他想更新$\red{K (1 <= K <= 20)}$条路经，将它们所须时间减为０．

帮助$\red{FJ}$选择哪些路经需要更新使得从１到$\red{N}$的时间尽量少.

输入格式

第一行: 三个空格分开的数: $\red{N, M, }$和 $\red{K }$

第$\red{2..M+1}$行: 第$\red{i+1}$行有三个空格分开的数：$\red{P1_i, P2_i, }$和 $\red{T_i}$

输出格式

第一行: 更新最多Ｋ条路经后的最短路经长度．

样例

输入样例

4 4 1
1 2 10
2 4 10
1 3 1
3 4 100

输出样例

1

提示

$\red{K}$是$\red{1}$;

更新道路$\red{3->4}$使得从$\red{3}$到$\red{4}$的时间由$\red{100}$减少到$\red{0}$

最新最短路经是$\red{1->3->4,}$总用时为１单位. $\red{N<=10000}$