Path#3355
In the country, there are cities. Travel between them is only possible via roads that connect certain pairs of cities. A path is defined as a sequence of cities A_1, A_2, ..., A_K, where all cities are distinct, K > 1, and for each i < K, there is a road between cities A_i and A_{i+1}. Each path has a length, which is the sum of the lengths of all roads between consecutive cities on the path. We will list all possible paths from city to city (i.e., A_1 = 1, A_K = N) in order of increasing length. If two paths have the same length, they will be ordered lexicographically. Find the first paths in this list (it is guaranteed that there will be at least paths).
The first line of the input contains three integers: - the number of cities, - the number of roads, and - the number of paths (1 \leq N \leq 20, 0 \leq M \leq N(N - 1), 1 \leq L \leq 30). The next lines each contain three integers S_i, T_i, C_i - the numbers of the cities connected by the -th road and its length (1 \leq S_i, T_i \leq N, S_i \neq T_i, 1 \leq C_i \leq 100). The numbers in the lines are separated by spaces.
Output lines, each representing a path as it appears in the list. The first number in each line is - the number of cities on the path, followed by numbers - the city numbers in the order they appear on the path. The numbers in the lines should be separated by spaces.
Example 1