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