In Search of Brides
Once upon a time, the king of Flatland decided to send k of his sons on a quest to find brides. Flatland is known to have n cities, some of which are connected by roads. The king resides in the capital, designated as city 1, while city n is renowned for its brides.
The king decreed that each son must travel from city 1 to city n using the roads. However, due to the limited number of beautiful brides in city n, the sons are cautious of each other and wish to ensure that no two of them use the same road, even if they travel at different times. The king, caring for his sons, desires that the average travel time for each son to reach city n is minimized.
Input
The first line contains the integers n, m, and k (2 ≤ n ≤ 200, 1 ≤ m ≤ 2000, 1 ≤ k ≤ 100), representing the number of cities, roads in Flatland, and the king's sons, respectively. The following m lines each contain three positive integers, indicating the cities connected by a road and the time required to travel it (with a maximum time of 10^6). Travel is possible in both directions, and multiple roads may connect the same pair of cities.
Output
If it is impossible to fulfill the king's order, output -1 on the first line. Otherwise, on the first line, output the minimum possible average travel time for the sons to reach city n, formatted to at least five decimal places. In the subsequent k lines, provide the paths for each son, starting with the number of roads in the path followed by the road numbers in the order they should be traveled. Roads are numbered starting from one, according to their order in the input.