题目背景

高速铁路缩短了城市之间的距离，也让不同交通线路的规划变得更加重要。国庆假期前，一片地区准备对现有铁路进行升级，希望旅客能够更快地从起点城市到达终点城市。

题目描述

这一地区共有 $n$ 个城市和 $m$ 条双向铁路，城市编号为 $1$ 到 $n$。第 $i$ 条铁路连接城市 $u_i$ 与城市 $v_i$，乘坐普通火车通过它需要 $w_i$ 的时间。

现在至多可以把 $k$ 条普通铁路升级为高铁。铁路升级后，通过该铁路所需的时间变为原来的 $\frac{1}{2}$。

每条铁路最多升级一次；也不要求恰好升级 $k$ 条铁路，可以只升级其中一部分，或者一条也不升级。

请计算从城市 $1$ 到城市 $n$ 所需的最短时间。

输入格式

第一行输入三个整数 $n,m,k$。

接下来 $m$ 行，每行输入三个整数 $u_i,v_i,w_i$，表示城市 $u_i$ 与城市 $v_i$ 之间存在一条双向铁路，乘坐普通火车通过它需要 $w_i$ 的时间。

输出格式

输出一个整数，表示从城市 $1$ 到城市 $n$ 的最短时间。

输入样例 #1

4 3 1
1 2 8
2 3 6
3 4 10

输出样例 #1

19

输入样例 #2

5 5 2
1 2 12
2 5 20
1 3 8
3 4 8
4 5 8

输出样例 #2

16

输入样例 #3

6 6 0
1 2 2
2 3 4
3 6 6
1 4 10
4 5 2
5 6 2

输出样例 #3

12

数据范围与约定

• 对于 $10\%$ 的数据，$k=0$；
• 对于 $50\%$ 的数据，$m\le100$；
• 对于 $70\%$ 的数据，$m\le500$；
• 对于 $100\%$ 的数据，$1\le n\le50$，$1\le m\le1500$，$0\le k\le50$；
• 所有 $w_i$ 均为偶数，保证答案为整数；
• 输入保证图连通、无自环、无重边。