T409013 「YAC Round 1」时间冻结

 > 琪露诺的算术教室开始了哟！要以像我一样的天才为目标！努力奋斗哦！！！

Cirno 一直在坚持冻结青蛙（~~洩矢诹访子~~）的冰之修行，终于有一天，Cirno 不再只会冻结青蛙了，她现在掌握了冻结时间的魔法！Cirno 自豪地称其为 *冻符「Time Freeze」（时间冻结）*。 Cirno 想借助 *冻符「Time Freeze」（时间冻结）* 的符卡（后面都统称为符卡）来实现快速飞行，以后就能更快地从雾之湖飞到妖怪之山进行冻青蛙的冰之修行啦（。 在幻想乡有 $N$ 个地点，$M$ 条双向的道路，地点编号为 $1$ ~ $N$。其中雾之湖的编号为 $1$，妖怪之山的编号为 $N$。 现在，Cirno 拥有 $K$ 张可以使时间变慢 $50 \%$ 的 符卡。在通过某条路径时，Cirno 可以选择使用一张符卡实现时间冻结，通过这一条道路的时间可以减少到原先的一半。 需要注意的是： 1. 在一条道路上最多只能使用一张 符卡。 2. 使用一张 符卡 只在一条道路上起作用。 3. 你不必使用完所有的 $K$ 张 符卡。 虽然 Cirno 掌握了时间冻结的魔法，但是她真是太笨了，完全不知道如何使用才能使得从雾之湖到妖怪之山（从地点 $1$ 到 地点 $N$）耗费的时间最短。 所以，请你帮帮 Cirno 求出在可以使用不超过 $K$ 张时间冻结的 符卡 之情形下，从雾之湖到妖怪之山（从地点 $1$ 到 地点 $N$）最少需要多长时间。

第一行包含三个整数：$N$、$M$、$K$。 接下来 $M$ 行，每行包含三个整数：$u_i$、$v_i$、$t_i$，表示地点 $u_i$ 与 地点 $v_i$ 之间存在一条双向道路，在不使用 符卡 的前提下，通过这条路径需要 $t_i$ 的时间。

输出一个整数，表示从雾之湖到妖怪之山（从点 $1$ 到 点 $N$）的最小用时。

#### 数据规模与约定 对于 $100\%$ 的数据，保证： - $1 \leq K \leq N \leq 50$，$M \leq 10^3$。 - $1 \leq u_i,v_i \leq N$，$2 \leq t_i \leq 2 \times 10^3$。 - 为保证答案为整数，保证所有的 $t_i$ 均为偶数。 - 所有数据中的无向图保证无自环、重边，且是连通的。