Tim Goodman si Detective Pikachu investighează sursa misteriosului gaz R care face pok emonii din Ryme City sa devina salbatici. Dupa o lunga sesiune de interogatoriu cu un Mr. Mime necooperativ, au reusit sa afle cateva informatii pretioase.

Sub Ryme City exista o retea formata din N puncte de control numerotate de la 0 la N-1, unite intre ele prin N-1 tuneluri bidirectionale, astfel incat exista un drum unic intre oricare doua puncte de control X[~i~] si Y[~i~] (0 ≤ i ≤ M-1), Mr. Mime a mers pe cel mai scurt drum si isi aminteste concentratia minima Z[~i~] a gazului R pe care a intalnit-i in punctele de control de pe acel drum.

Sub Ryme City exista o retea formata din N puncte de control numerotate de la 0 la _N_-1, unite intre ele prin _N_-1 tuneluri bidirectionale, astfel incat exista un drum unic intre oricare doua puncte de control _X ~i~_ si _Y ~i~_ (0 ≤ _i_ &le _M_-1), Mr. Mime a mers pe cel mai scurt drum si isi aminteste concentratia minima _Z ~i~_ a gazului R pe care a intalnit-i in punctele de control de pe acel drum.

Ultima informatie data de Mr. Mime este ca, foarte probabil, toate mai putin doua dintre punctele de control au exact doua tuneluri adiacente.

h2. Date de intrare

* linia 1: N M ,reprezentand numarul de puncte de control, respectiv numarul de informatii despre retea
* linia 2 + i  (0 ≤ i ≤ M-1): X[~i~] Y[~i~] Z[~i~] reprezentand informatiile oferite de Mr.Mime.

* linia 1: _N_ _M_ ,reprezentand numarul de puncte de control, respectiv numarul de informatii despre retea
* linia 2 + _i_ (0 ≤ _i_ ≤ _M_-1): _X ~i~_ _Y ~i~_ , _Z ~i~_ reprezentand informatiile oferite de Mr.Mime.

Fişierul de intrare $detective.in$ ...
h2. Date de ieşire

Fisierul de iesire va contine N-1 perechi (x,y) , reprezentând două puncte de control unite de un tunel.

Fisierul de iesire va contine _N-1_ perechi (x,y) , reprezentând două puncte de control unite de un tunel

h2. Punctare

h2. Restricţii

* $... ≤ ... ≤ ...$