h2. Date de intrare

N, M, M perechi (a, b, c) cu semn. c = lca(a, b)

Pe prima linie a fisierului $revolve.in$ se afla cele doua numere naturale <tex>N</tex> si <tex>M</tex>, cu semnificatia din enunt. Pe urmatoarele M linii se afla cate un triplet de numere <tex>a_i, b_i, c_i </tex> cu semnificatia <tex> textbf{ lca(a_i , b_i ) = c_i } </tex> .

h2. Date de ieşire

Pt fiecare test
-1 daca nu se poate
Daca se poate:
 
R (radacina)
N-1 perechi (a, b) -> muchii

În fişierul de ieşire $revolve.out$ ...

h2. Restricţii

N, M <= 1e5
suma de M-uri nu depaseste 5e5

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

h2. Exemplu