In Search of Brides#3509
Once upon a time, the king of Flatland decided to send of his sons on a quest to find brides. Flatland is known to have cities, some of which are connected by roads. The king resides in the capital, designated as city , while city is renowned for its brides.
The king decreed that each son must travel from city to city using the roads. However, due to the limited number of beautiful brides in city , 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 is minimized.
The first line contains the integers , , and (2 \leq n \leq 200, 1 \leq m \leq 2000, 1 \leq k \leq 100), representing the number of cities, roads in Flatland, and the king's sons, respectively. The following 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.
If it is impossible to fulfill the king's order, output on the first line. Otherwise, on the first line, output the minimum possible average travel time for the sons to reach city , formatted to at least five decimal places. In the subsequent 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.
Örnek 1