В стране \textbf{N} городов. Перемещаться между ними можно только по дорогам, которые есть между некоторыми парами городов. Путем назовем список городов \textbf{A_1}, \textbf{A_2}, ..., \textbf{A_K}, такой, что все города в нем различны, \textbf{K} > \textbf{1} и для всех \textbf{i} < \textbf{K} есть дорога между городами \textbf{A_i} и \textbf{A_\{i+1\}}. У каждого пути есть длина - сумма длин всех дорог между соседними в пути городами. Упорядочим все возможные пути из города \textbf{1} в город \textbf{N} (то есть \textbf{A_1} = \textbf{1}, \textbf{A_K }=\textbf{ N}) по увеличению их длины, а в случае двух путей одинаковой длины - их упорядочим в лексикографическом порядке. Найдите \textbf{L} первых путей в этом списке (гарантируется, что путей будет не меньше \textbf{L}). \InputFile Первая строка входного файла содержит три целых числа \textbf{N} - количество городов, \textbf{M} - количество дорог, и \textbf{L} - количество путей (\textbf{1} ≤ \textbf{N} ≤ \textbf{20}, \textbf{0} ≤ \textbf{M} ≤ \textbf{N(N - 1)}, \textbf{1} ≤ \textbf{L} ≤ \textbf{30}). Следующие \textbf{M} строк содержат по три целых числа \textbf{S_i}, \textbf{T_i}, \textbf{C_i} - номера городов, соединенных \textbf{i}-й дорогой и ее длина (\textbf{1} ≤ \textbf{S_i}, \textbf{T_i} ≤ \textbf{N}, \textbf{S_i} ≠ \textbf{T_i}, \textbf{1} ≤ \textbf{C_i} ≤ \textbf{100}). Числа в строках разделены пробелами. \OutputFile В выходной файл выведите \textbf{L} строк - пути, как они идут в списке. Первое число в каждой строке - \textbf{K} - количество городов в найденном пути, следующие \textbf{K} чисел - номера городов в том порядке, в котором они идут в найденном пути. Числа в строках должны быть разделены пробелами.