旅行

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 travela.in 输出文件 travela.out

【问题描述

一天,TZD想从0号村庄游历到n-1号村庄,这n个村庄由m条有向路连接,某两个村庄间可能有多条路相连。
当他在处于同一个强连通分支中的两个村庄间游历时,他可以租辆自行车来骑着,否则的话,就只能步行了。说的再详细点,对于从村庄a到村庄b的每一条路,如果这两个村庄处在同一个强连通分支中,(这意味着你可以从a到达b,也可以从b到达a)那么你可以租一辆自行车来骑行,所用时间为time[a][b]分钟,否则你必须步行通过,所用时间为2*time[a][b]分钟。
TZD想尽快到达目的地,他希望在此过程中步行的路不超过k条。现在你需要为他计算出:在满足步行的路不超过k条的情况下,到达目的地所用的最短时间。


【输入格式】
  输入文件有一组或多组数据每一组数据的第一行有三个整数:n,m,k,含义如上所述(1<=n<=100,  0<=m<=100 000,   0<=k<=10)。
接下来有m行,每行有3个整数a,b,time[a][b],表示从村庄a至村庄b有一条路,骑自行车需time[a][b]分钟,而步行则需2*time[a][b]分钟。(0<=a,b<=n-1 输入文件以单独的一行3个0表示结束。

【输出格式】


  对于每一组测试数据,在一行输出其答案,如果TZD无法在步行不超过k条路的情况下到达目的地,则输出-1。

【样例】

travela.in
5 6 3
0 1 1
0 2 2
2 1 1
1 3 3
3 1 3
3 4 2
0 0 0

travela.out
9