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