Path
In the country, there are N 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 1 to city N (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 L paths in this list (it is guaranteed that there will be at least L paths).
Input
The first line of the input contains three integers: N - the number of cities, M - the number of roads, and L - the number of paths (1 ≤ N ≤ 20, 0 ≤ M ≤ N(N - 1), 1 ≤ L ≤ 30). The next M lines each contain three integers S_i, T_i, C_i - the numbers of the cities connected by the i-th road and its length (1 ≤ S_i, T_i ≤ N, S_i ≠ T_i, 1 ≤ C_i ≤ 100). The numbers in the lines are separated by spaces.
Output
Output L lines, each representing a path as it appears in the list. The first number in each line is K - the number of cities on the path, followed by K numbers - the city numbers in the order they appear on the path. The numbers in the lines should be separated by spaces.