You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

“我要成为魔法少女！”

“那么，以灵魂为代价，你希望得到什么？”

“我要将有关魔法和奇迹的一切，封印于卡片之中„„”

在这个愿望被实现以后的世界里，人们享受着魔法卡片（SpellCard，又名符卡）带来的便捷。

现在，不需要立下契约也可以使用魔法了！你还不来试一试？

比如，我们在魔法百科全书（Encyclopedia of Spells）里用“freeze”作为关键字来查询，会有很多有趣的结果。

例如，我们熟知的 Cirno，她的冰冻魔法当然会有对应的 SpellCard 了。当然，更加令人惊讶的是，居然有冻结时间的魔法，Cirno 的冻青蛙比起这些来真是小巫见大巫了。

这说明之前的世界中有很多魔法少女曾许下控制时间的愿望，比如 Akemi Homura、Sakuya Izayoi、……

当然，在本题中我们并不是要来研究历史的，而是研究魔法的应用。

题目描述

我们考虑最简单的旅行问题吧： 现在这个大陆上有 $N$ 个城市，$M$ 条双向的道路。城市编号为 $1$ ~ $N$，我们在 $1$ 号城市，需要到 $N$ 号城市，怎样才能最快地到达呢？

这不就是最短路问题吗？我们都知道可以用 Dijkstra、Bellman-Ford、Floyd-Warshall等算法来解决。

现在，我们一共有 $K$ 张可以使时间变慢 50%的 SpellCard，也就是说，在通过某条路径时，我们可以选择使用一张卡片，这样，我们通过这一条道路的时间 就可以减少到原先的一半。需要注意的是：

1. 在一条道路上最多只能使用一张 SpellCard。
2. 使用一张SpellCard 只在一条道路上起作用。
3. 你不必使用完所有的 SpellCard。

给定以上的信息，你的任务是：求出在可以使用这不超过 $K$ 张时间减速的 SpellCard 之情形下，从城市 $1$ 到城市 $N$ 最少需要多长时间。

输入格式

第一行包含三个整数：$N$、$M$、$K$。

接下来 $M$ 行，每行包含三个整数：$A_i$、$B_i$、$Time_i$，表示存在一条 $A_i$ 与 $B_i$ 之间的双向道路，在不使用 SpellCard 之前提下，通过它需要 $Time_i$ 的时间。

输出格式

输出一个整数，表示从 $1$ 号城市到 $N$ 号城市的最小用时。

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

7

提示

样例 1 解释

在不使用 SpellCard 时，最短路为 $1 \to 2 \to 4$，总时间为 10。现在我们可以使用 1 次 SpellCard，那么我们将通过 $2 \to 4$ 这条道路的时间减半，此时总时间为7。

数据规模与约定

对于 $100\%$ 的数据，保证：

• $1 \leq K \leq N \leq 50$，$M \leq 10^3$。
• $1 \leq A_i,B_i \leq N$，$2 \leq Time_i \leq 2 \times 10^3$。
• 为保证答案为整数，保证所有的 $Time_i$ 均为偶数。
• 所有数据中的无向图保证无自环、重边，且是连通的。