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

Есеп B. Жол

Ограничение по времени:

2 секунд

Ограничение по памяти:

256 мегабайт

Мемлекетте $N$ қала бар. Тек қана кейбір қалалар арасында бар белгілі жүрістермен арқылы ауысуға болады. $K > 1$ және әр $i < K$ үшін $A_i$ және $A_{i + 1}$ арасында жол бар, $A_1$, $A_2$, ... $A_K$ қалалар тізімін жол деп атаймыз. Әр жолдың ұзындығы, яғни жолдағы көршілес қалалар арасындағы жүрістердің қосындысы бар. $1$-ші қаладан $N$-ші қалаға дейнгі барлық жолдарды ұзындығының өсуі бойынша реттейік, ал егер екі жолдың ұзындығы бірдей болса, онда лексиграфиялық тәртіппен реттейміз. Осы тізімдегі алғашқы $L$ жолды табыңыз (жолдардың саны $L$-ден аз болмайтынына кепіл беріледі).

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

Енгізу файлының бірінші жолында үш бүтін сан $N$ — қалалар саны, $M$ — жолдар саны және $L$ ($1 \le N \le 20$, $0 \le M \le N(N - 1)$, $1 \le L \le 30$). Келесі $M$ жолдың әрқайсысы үш бүтін саннан $S_i$, $T_i$ — $i$-ші жол қосатын қалалардың нөмірлері, $C_i$ — оның ұзындығы тұрады ($1 \le S_i, T_i \le N$, $S_i \ne T_i$, $1 \le C_i \le 100$). Жолдардағы сандар бос орынмен бөлінген.

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

Шығару файлға $L$ жолды — табу керек $L$ жолды тізімдеғі ретімен шығарыңыз. Әр жолдағы бірінші сан $K$ — табылған жолдағы қалалар саны, келесі $K$ сан — қалалардың табылған жолдағы ретімен шығар. Жолдағы сандар бос орынмен бөлінген.

Пример:

Вход

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

Ответ

3 1 3 4
3 1 2 4