旅行

【问题描述】

一天，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