魔卡
时间限制：1秒 内存限制：256M
【问题描述】
现在这个大陆上有 \(N\) 个城市，\(M\) 条双向的道路。城市编号为 \(1..N\)，我们在 1 号城市，需要到 \(N\) 号城市，怎样才能最快地到达呢？
现在，我们一共有 \(K\) 张可以使时间变慢 50% 的魔卡，也就是说，在通过某条路径时，我们可以选择使用一张卡片，这样，我们通过这一条道路的时间就可以减少到原先的一半。需要注意的是：
1. 在一条道路上最多只能使用一张魔卡。
2. 使用一张魔卡只在一条道路上起作用。
3. 你不必使用完所有的魔卡。
给定以上的信息，你的任务是：求出在可以使用这不超过 \(K\) 张时间减速的魔卡之情形下，从城市 1 到城市 \(N\) 最少需要多长时间。
【输入格式】
第一行包含三个整数：\(N、M、K\)。
接下来 \(M\) 行，每行包含三个整数：\(A_i、B_i、T_i\)，表示存在一条 \(A_i\) 与 \(B_i\) 之间的双向道路，在不使用魔卡 之前提下，通过它需要 \(T_i\) 的时间。
【输出格式】
输出一个整数，表示从 1 号城市到 \(N\) 号城市的最小用时。
【输入输出样例】
Input
4 4 1
1 2 4
4 2 6
1 3 8
3 4 8
Output
7
【数据限制】
对于 \(100\%\) 的数据：\(1 ≤ K ≤ N ≤ 100，M ≤ 1000。1≤ A_i,B_i ≤ N，2 ≤ T_i ≤ 2000\)。 为保证答案为整数，保证所有的 \(T_i\) 均为偶数。所有数据中的无向图保证无自环、重边，且是连通的。
