ulei

Dezamăgit de afacerea Siragul, Lunasorab s-a gândit să plece în vacanţă la Paris. A decis să încerce lucruri noi, cum ar fi vizitarea unei galerii de artă. Galeria are mai multe tipuri de tablouri, însă cele care il interesează cel mai mult pe Lunasorab sunt cele în ulei (de mic copil i-a plăcut sa schimbe uleiul la maşină). Galeria este formată din $N$ camere care comunică între ele prin $M$ coridoare, iar tablourile în ulei se găsesc numai pe coridoare, câte unul pe fiecare coridor. Fiecare tablou este pictat cu un tip anume de ulei. Cum nu umblă cu jumătăti de masură, Lunasorab ar vrea să vadă toate tablourile în ulei. Fiind prima lui vizită la muzeu, el doreşte să vadă fiecare tablou exact o dată (în momentul în care trece printr-un coridor Lunasorab vede tabloul care se află acolo). De asemenea, pentru a nu se plictisi, el nu vrea sa vadă două tablouri consecutive care folosesc acelaşi tip de ulei şi nu vrea să termine vizita în muzeu cu un tablou pictat cu acelaşi tip de ulei ca primul tablou văzut. El nu poate să treacă dintr-o cameră în alta decât prin coridorul care le uneşte şi va trece prin fiecare coridor exact o dată. De asemenea, secvenţa de coridoare parcursă nu conţine $2$ tablouri consecutive pictate în acelaşi tip de ulei. În plus, tipul primului tablou văzut trebuie să fie diferit de cel al ultimului tablou vizitat. Vizita începe şi se termină din aceeaşi cameră.

De aceea, el vă cere ajutorul, promiţându-vă o parte din profitul următoarei sale afaceri. Pentru a fi sigur ca nu îl păcăliţi, el vă va furniza mai multe planuri de galerii, alegând la sfârşit pe cel care-i place cel mai mult.

Cerinţă

Dându-se planul galeriei, găsiţi o secvenţă de coridoare prin care să treacă Lunasorab.

Date de intrare

Fişierul de intrare ulei.in va conţine pe prima linie numărul natural $T$, reprezentând numărul de teste. Pe urmatoarele linii vor urma $T$ teste, descrise în continuare. Fiecare test este format din $M + 1$ linii. Prima linie va conţine $N$ si $M$, reprezentând numărul de camere precum şi numărul de coridoare. Pe urmatoarele $M$ linii se vor afla coridoarele, unul pe linie, date sub forma $i \ j \ t$, semnificând faptul că există un coridor de la camera $i$ la camera $j$, conţinând un tablou care foloseste tipul $t$ de ulei. Coridoarele sunt bidirecţionale, iar între aceeaşi pereche de camere poate exista cel mult un coridor.

Date de ieșire

Fişierul de ieşire ulei.out va conţine $T$ linii. Pe fiecare linie se găseşte o secvenţă de $M + 1$ de numere naturale separate prin câte un spaţiu, reprezentând numerele camerelor în ordinea vizitării.

Restricții și precizări

• $1 \leq T \leq 5$
• $1 \leq N \leq 15 \ 000$
• $1 \leq M \leq 100 \ 000$
• Nu va exista coridor de la o cameră la ea însăşi
• Pe testele folosite la evaluare va exista mereu soluţie
• Tipurile de ulei vor fi între $1$ si $15 \ 000$
• Pentru $20\%$ din teste vor fi doar $2$ tipuri de ulei

Exemplul 1

ulei.in

1
3 3
1 2 1
2 3 2
3 1 3

ulei.out

1 2 3 1

Explicație

Lunasorab începe vizita în camera $1$, continuând cu camerele $2$ si $3$, revenind în final în camera $1$. Astfel, el a vizitat toate tablourile şi nu s-a plictisit.