eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Путь

Путь

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

В стране 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 - количество путей (1N20, 0MN(N - 1), 1L30). Следующие M строк содержат по три целых числа S_i, T_i, C_i - номера городов, соединенных i-й дорогой и ее длина (1S_i, T_iN, S_iT_i, 1C_i100). Числа в строках разделены пробелами.

Выходные данные

В выходной файл выведите L строк - пути, как они идут в списке. Первое число в каждой строке - K - количество городов в найденном пути, следующие K чисел - номера городов в том порядке, в котором они идут в найденном пути. Числа в строках должны быть разделены пробелами.

Пример

Входные данные #1
5 5 1
1 4 87
2 3 16
3 4 91
3 5 22
5 4 27
Выходные данные #1
3 1 4 5
Источник Открытый личный чемпионат ИГЭУ, Иваново, 20.05.2011