问题 25257 --传送门

25257: 传送门

时间限制: 10 Sec  内存限制: 128 MB
提交: 240  解决: 85
[提交][状态][讨论版][数据上传:][下载FPS10元][下载测试数据10元][3604kb]

题目描述

FJ 每天都要从家里去牧场,再从牧场回家……

FJ从家到牧场的地区可以看作一个N个点和M条双向边的图,家在1号点,牧场在N号点。现在FJ掌握了现代科技,他现在要将一些道路的两端修建双向传送的传送门,这样可以把通过的时间变为0现在FJ最多可以建K个传送门,FJ想知道他从家到牧场最少需要多少时间?

输入

第一行,三个数NMK

接下来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

来源

[提交][状态]