站外题求助（或者给出洛谷原题）

传送门
内存限制：256 MiB
时间限制：1000 ms
标准输入输出
题目类型：传统
评测方式：文本比较
题目描述
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
数据范围与提示
对于100%的数据，N<=10000,M<=50000,K<=20，答案在int 范围内 对于测试点1~6，时限1s 对于测试点7~9，时限3s 对于测试点10，时限10s