时间限制：1秒　　内存限制：256M

---

【题目描述】

　　每天农夫约翰从牧场1 需要经过一些道路去检查牛棚 \(n\) 里面的牛。农场上有 \(m\) 条双向泥土道路（编号为 \(1..m\)）。道路 \(i\) 连接牛棚 \(a_i\) 和 \(b_i\)， 约翰需要 \(t_i\) 时间单位用道路 \(i\) 从 \(a_i\) 走到 \(b_i\) 或者从 \(b_i\) 走到 \(a_i\)。

　　约翰打算升级其中 \(k\) 条小路，使之成为高速公路。在高速公路上的通行几乎是瞬间完成的，所以高速公路的通行时间为 0。 请帮助约翰决定对那些小路进行升级，使他每天早上到牧场 \(n\) 的时间最少。输出这个最少时间。

【输入格式】

　　第一行是三个空格分开的数: \(n, m\) 和 \(k\)，之后的 \(m\) 行，第 \(i+1\) 行有三个空格分开的数：\(a_i, b_i\) 和 \(t_i\)

【输出格式】

　　\(k\) 条小径升级后，约翰每天早上花在路上的最少时间。

【输入输出样例】

　Input

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

　Output

1

【输入输出样例解释】

　　\(k\) 是 1，更新道路 3->4 使得从 3 到 4 的时间由 100 减少到 0。 最新最短路经是 1->3->4，总用时为 1 单位.

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤10000\)，\(1≤m≤50000\)，\(1≤k≤20\)，\(1≤t_i≤10000\)。

【来源】

　　Mr.he