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