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

Есеп B. Жол

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

2 секунд

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

256 мегабайт

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

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

Енгізу файлының бірінші жолында екі бүтін сан $N$ — қалалар саны, $M$ — жолдар саны ($1 \le N \le 20, 0 \le M \le N(N - 1)$). Келесі $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$). Жолдардағы сандар бос орынмен бөлінген.

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

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

Пример:

Вход

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

Ответ

3 1 3 4
3 1 2 4