题目描述

WJJ 喜欢旅游，这次她打算去一个据说有很多漂亮瀑布的山谷玩。

WJJ 事先得到了一张地图，上面标注了 $N$ 个小动物的聚居地，也就是一个个的小村落。其中第 $1$ 个村庄是 WJJ 现在住的地方，第 $N$ 个村庄是 WJJ 打算去的地方。

这些村庄之间有 $M$ 条双向道路连接着，第 $i$ 条双向道路恰好直接连接两个小村庄 $A_i$，$B_i$，长度为 $C_i$。道路有的是隧道，有的是栈桥，地图上那些看起来在村庄之外交叉的路实际上并不相交——也就是说，如果把这些小村落和双向道路构成的道路网看作图论意义上的图，我们不保证它是平面图，也不保证它没有重边。不过，有一点还是可以保证的：WJJ 细心地验证过，从它居住的村落一定能走到她想去的那个山谷。

在 WJJ 所在的神奇世界中，每只小动物都可以借助仙人掌来施放魔法，其中之一是，交换世界中任意两条双向道路的长度，同时保持其他道路的长度不变。按 WJJ 目前的魔法水平，她最多能使用 $K$ 次这种道路长度交换魔法。可惜的是，由于仙人掌刺比较多，WJJ 并不打算带着它旅行，于是她会在家里完成想要的道路交换后再出门。

假设 WJJ 的旅行途中不会有其他小动物进行道路交换来破坏她设计好的路线。为了尽快达到目的地，WJJ 希望她需要走的总距离越短越好。也就是说，使用最多 $K$ 次魔法后，从村落 $1$ 到村落 $N$ 的最短距离是多少？

输入格式

第一行为 $3$ 个用空格隔开的整数 $N,M,K$。

接下来 $M$ 行，每行 $3$ 个整数，用空格隔开，分别表示 $A_i,B_i,C_i$。

输出格式

一个整数，表示使用最多 $K$ 次魔法后，村落 $1$ 和村落 $N$ 之间的最短距离。

5 5 2
1 2 10
2 5 10
1 3 4
3 4 2
4 5 1

3

提示

样例解释

一个可行的方案是，对调第 $1$ 条边和第 $4$ 条边的长度，再对调第 $2$ 条边和第 $5$ 条边的长度。对调后的最短路径为 $1\rightarrow 2\rightarrow 5$，长度为 $3$。可以证明，没有比这更优的方案了。

数据范围

对于 $100\%$ 的数据，$1\leq N\leq 50$，$1\leq M\leq 150$，$1\leq K\leq 20$，$1\leq A_i,B_i\leq N$，$A_i\neq B_i$，$1\leq C_i\leq 1000$。