Путь
В стране 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).
Input
Первая строка входного файла содержит три целых числа 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). Числа в строках разделены пробелами.
Output
В выходной файл выведите L строк - пути, как они идут в списке. Первое число в каждой строке - K - количество городов в найденном пути, следующие K чисел - номера городов в том порядке, в котором они идут в найденном пути. Числа в строках должны быть разделены пробелами.