21620_Trave

One day TZD wants to go from village 0 to village n-1. There are m directed roads connecting the n villages. There may be more than one road from a village to another village.

When he travels between villages in the same strongly connected component, he can rent a bike. Otherwise, he has to walk. More precisely, for each road from village a to village b, if the two villages are in the same strongly connected component (meaning that you can go from village a to village b and also from village b to village a) then you can rent a bike and travel through the road in time[a][b] minutes. Otherwise you have to travel through it on foot in 2*time[a][b] minutes.

TZD wants to get to his destination as quickly as possible and he expects that the number of roads he travels on foot is no more than k. Now you are asked to find the shortest time that TZD can reach his destination with the number of roads he travels on foot no more than k.

The input may contain several test cases.

Each test case starts with a line containing three integer n, m and k. Each is described above. ( 1 ≤ n ≤ 100,  0 ≤ m ≤ 100000,  0 ≤ k ≤ 10 ).

The next m lines each contain three integer a, b and time[a][b], meaning that there is a road from village a to village b and it takes time[a][b] minutes to travel through the road by bike, 2*time[a][b] minutes on foot. ( 0 ≤ a, b ≤ n-1,  0 < time[a][b] ≤ 10000 )

Input is terminated by one line contains three zeros.

For each test case print the answer in a single line. If TZD can't get to his destination with the number of roads he travels on foot no more than k, print -1.

5 6 3
0 1 1
0 2 2
2 1 1
1 3 3
3 1 3
3 4 2
0 0 0

9