Республиканская олимпиада по информатике 2010 года за 11 класс | Казахстанские олимпиады

Задача B. Путь

Ограничение по времени Ограничение по памяти
2 секунды 256 мегабайт

В стране NN городов. Перемещаться между ними можно только по дорогам, которые есть между некоторыми парами городов. Путем назовем список городов A1A_1, A2A_2, ... AKA_K, такой, что все города в нем различны, K>1K > 1 и для всех i<Ki < K есть дорога между городами AiA_i и Ai+1A_{i + 1}. У каждого пути есть длина — сумма длин всех дорог между соседними в пути городами. Упорядочим все возможные пути из города 11 в город NN (то есть A1=1A_1 = 1, AK=NA_K = N) по увеличению их длины, а в случае двух путей одинаковой длины — их упорядочим в лексикографическом порядке. Найдите LL первых путей в этом списке (гарантируется, что путей будет не меньше LL).

Формат входного файла

Первая строка входного файла содержит три целых числа NN — количество городов, MM — количество дорог, и LL — количество путей (1N201 \le N \le 20, 0MN(N1)0 \le M \le N(N - 1), 1L301 \le L \le 30). Следующие MM строк содержат по три целых числа SiS_i, TiT_i, CiC_i — номера городов, соединенных ii-й дорогой и ее длина (1Si,TiN1 \le S_i, T_i \le N, SiTiS_i \ne T_i, 1Ci1001 \le C_i \le 100). Числа в строках разделены пробелами.

Формат выходного файла

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

Примеры

Вход

4 4 2
1 2 3
1 3 1
2 4 4
3 4 2

Выход

3 1 3 4
3 1 2 4