== include(page="template/taskheader" task_id="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 Lunasorb 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ă.
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.
h2. Cerinta
Dându-se planul galeriei, găsiţi o secvenţă de coridoare prin care să treacă Lunasorb.
Dându-se planul galeriei, găsiţi o secvenţă de coridoare prin care să treacă Lunasorab.
h2. 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 urrma $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.
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 urrma $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.
h2. Date de ieşire
