题目描述

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

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

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

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

输入格式

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

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

输出格式

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

样例

输入样例

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

输出样例

1

提示

${K}$是${1}$;

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

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