Penalization
By Thalyson Nepomuceno, UECE 
Brazil
By Thalyson Nepomuceno, UECE Brazil
In the game Pomekon, one of the goals is to visit real places to get new items and experience. Fulyane does not like to leave the house, she made a program that simulates its location, providing false coordinates of her location to the game. She also made a romote control that allows to move with fake coordinates, pretending as if she were really walking, but without leaving home.
Searching forums, she found that for not to be banned from the game, she would have to move using only the real routes, but also found that he could move instantly from one place to another, without using real routes no more than K times per day, because if she to teleport more than K times, she could be banned from the game forever.
Fulyane always starts at the location identified by the index 1, and wants to visit the all locations, using the teleport no more than K times.
The input contains several instances. The first line of input contains an integer T indicating the number of instances. The first line in each instance contains three integers N (1 ≤ N ≤ 15), M (1 ≤ M ≤ N2) and K (0 ≤ K ≤ 5) representing respectively the number of locations, number of routes and the amount maximum allowable of teleporters. Then, follows M lines, each line containing three integers A, B and C (1 ≤ C ≤ 30000), representing respectively that the location A is connected with the location B by a route, and Fulyane takes C minutes to get from A to B using this route.
For each instance, print the minimum amount of minutes that Julyane takes to visit all locations, using no more than K teleporters. If you can not visit all places, print -1.
| Input Sample | Output Sample |
|
2 |
7 |