У країні \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} чисел - номери міст у тому порядку, у якому вони йдуть на знайденому шляху. Числа в рядках повинні бути відокремлені пропусками.