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