Extra
Time
BZOJ1579 道路升级 Time:1s Memory:50M AC:0% Submit:4

Description

每天,农夫 John 需要经过一些道路去检查牛棚 N 里面的牛. 农场上有 M(1<=M<=50,000)条双向泥土道路,编号为 1..M. 道路 i 连接牛棚P1_iP2_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 走到 P1_i 他 想更新一些路经来减少每天花在路上的时间.具体地说,他想更新 K (1 <= K <= 20)条路经,将它们所须时间减为0.帮助 FJ 选择哪些路经需要更新 使得从1到 N 的时间尽量少.

Input

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

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

Output

* 第一行: 更新最多K条路经后的最短路经长度.

Sample Input

4 4 1

1 2 10

2 4 10

1 3 1

3 4 100

Sample Output

1

HINT

K 是 1; 更新道路 3->4 使得从3到4的时间由100减少到0. 最新最短 路经是 1->3->4,总用时为1单位. N<=10000