Description
FJ 每天都要从家里去牧场，再从牧场回家…… FJ 从家到牧场的地区可以看作一个 N 个点和 M 条双向边的图，家在 1 号点，牧场在 N 号点。现在 FJ 掌握了现代科技，他现在要将一些道路的两端修建双向传送的传送门，这样可以把通过的时间变为 0 。现在 FJ 最多可以建 K 个传送门，FJ 想知道他从家到牧场最少需要多少时间？
Input
第一行，三个数 N，M，K。 接下来M行，每行三个数，表示一条边的两端和长度
4 4 1
1 2 10
2 4 10
1 3 1
3 4 100
HINT
N <= 10000，M <= 50000，K <= 20