By João Marcos Salvanini Bellini de Moraes, IFSULDEMINAS Brazil
Garoto Ixpertinho is back. Just like before, he still wants everybody to know the meaning and the origin of the word Malakoi, but this time, he's really serious. Garoto Ixpertinho wants to spread this world all over the city, and always in the usual way, that is, dancing his typical dance. However, he won't have enough breath to walk every block while screaming and dancing at the same time
As a result, some blocks will end up not being visited and he won't be able to accomplish his life mission. Keeping this in mind, Garoto Ixpertinho contacted some of his friends and fans all around the city, so he can rest, feed and resume his journey, when he loses his breath on the way between a block and another.
Thus, Garoto Ixpertinho wants to spread his word to every single person in the city, visiting every single block in the shortest possible time. He doesn't mind visiting the same block again, because from the second visit, he'll no longer need to spread his word to that block, and this time won't be added to the time of the main journey.
Besides, every time he visits a block (having lost his breath on the way or not), he rests and gets all the breath again, but this rest time must be ignored. On the other hand, when he loses his breath on the way between a block and another, he takes exactly 2 minutes to feed, and this time must be considered.
The input contains several test cases. Each test case starts with two integers Q (2 ≤ Q ≤ 1000) and C (Q-1 ≤ C ≤ 1000) and a real number T (1 ≤ T ≤ 30), indicating, respectively, the number of blocks, the number of paths that connect them and the maximum time, in minutes, that Garoto Ixpertinho can keep screaming and dancing at the same time. The following C inputs of two integers X and Y and a real number Z (1 ≤ Z ≤ 60) indicates that he takes Z minutes to go from the block X to the block Y spreading the word Malakoi. Consider that there's always at least one way to reach a block. Read input until Q = C = T = 0.
For each test case, print the minimum time it takes for Garoto Ixpertinho to visit every block (with accuracy of two decimal places), and in the same line, how many times he had to feed, that is, how many times he lost his breath on the way between a block and another.
|Input Sample||Output Sample|
4 4 2.6
1 2 3.9
1 3 5.1
2 3 1.1
2 4 1.6
5 6 2.01
1 2 2.01
3 4 9.8
2 4 8.73
1 4 2.009
2 3 3.62
5 4 5
0 0 0