Yol
Ölkədə N şəhər mövcuddur. Şəhərlər arasında yalnız bəzi cütlər arasında yollarla hərəkət etmək mümkündür. Bir yolu, A_1, A_2, ..., A_K şəhərlər ardıcıllığı kimi təyin edəcəyik, burada bütün şəhərlər fərqlidir, K > 1 və hər i < K üçün A_i və A_{i+1} şəhərləri arasında bir yol mövcuddur. Hər yolun uzunluğu var - bu, yoldakı qonşu şəhərlər arasında olan bütün yolların uzunluqlarının cəmidir. Şəhər 1-dən şəhər N-ə (yəni A_1 = 1, A_K = N) olan bütün mümkün yolları uzunluqlarının artma sırasına görə sıralayacağıq və iki yol eyni uzunluqda olduqda, onları leksikoqrafik sıraya görə sıralayacağıq. Bu siyahıda ilk L yolları tapın (yolların L-dən az olmayacağı təmin edilir).
Giriş verilənləri
Giriş faylının ilk sətiri üç tam ədəd N - şəhərlərin sayı, M - yolların sayı və L - yolların sayı (1 ≤ N ≤ 20, 0 ≤ M ≤ N(N - 1), 1 ≤ L ≤ 30) ehtiva edir. Növbəti M sətir hər biri üç tam ədəd S_i, T_i, C_i - i-ci yol ilə birləşdirilən şəhərlərin nömrələri və onun uzunluğu (1 ≤ S_i, T_i ≤ N, S_i ≠ T_i, 1 ≤ C_i ≤ 100) ehtiva edir. Sətirlərdəki ədədlər boşluqlarla ayrılmışdır.
Çıxış verilənləri
Çıxış faylına siyahıda olduğu kimi L sətir yazın. Hər bir sətirdə ilk ədəd tapılan yoldakı şəhərlərin sayı olan K, növbəti K ədəd isə tapılan yoldakı şəhərlərin nömrələri, onların tapılan yoldakı sırasına uyğun olaraq yazılmalıdır. Sətirlərdəki ədədlər boşluqlarla ayrılmalıdır.