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_ &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.

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.

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. Restricţii

h2. Punctare

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

Pentru orice test punctajul maxim se obtine dacă reteaua produsă nu contrazice informatiile produse de Mr. Mime, si în plus, toate mai putin două dintre punctele de control au exact două tuneluri adiacente.
 
|_. Subtask |_. Punctaj|_. Constrangeri |
|1           | 40 de puncte  |  1 ≤ N ≤ 1000
                               0 ≤ M ≤ 2000             |
|2           | 10 de puncte   | 1 ≤ N &le 500
                                0 ≤ M ≤ 250000
                                Oricare ar fi 0 ≤ a,b &le N-1 exista un drum i parcurs de Mr. Mime astfel incat X[~i~]=a si Y[~i~]=b |
|3           | 50 de puncte   | 1 ≤ N,M &le 250000 |

h2. Exemplu
table(example). |_. detective.in |_. detective.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 5 10
3 0 0
3 4 0
3 1 0
3 2 0
0 4 0
0 1 0
0 2 0
4 1 1
4 2 1
1 2 1
| 3 0
0 4
4 1
1 2

|
h3. Explicaţie

O posibilă retea de tuneluri si puncte de control este reprezentată în următoarea imagine:
 
!problema/detective?graph4.png!
 
Următoarea retea reprezentată nu este însă corectă deoarece concentratia minimă de gaz R observată
de Mr. Mime pe drumul de la 4 la 2 este 1, dar reteaua ar indica că această concentratie este 2.
 
!problema/detective?graph5.png!
 

...
== include(page="template/taskfooter" task_id="detective") ==