}
==

Observam mai multe deficiente in codul de mai sus. Pe langa documentatia rudimentara, mai avem faptul ca Por Costel isi retine graful printr-un vector de muchii (vectorul <tex>E</tex>). O muchie este retinuta ca un triplet (x, y, z) cu semnficiatie ca muchia porneste de la x la y si are costul z. Dar cel mai rau probabil este faptul ca programul este LENT !

Observam mai multe deficiente in codul de mai sus. Pe langa documentatia rudimentara, mai avem faptul ca Por Costel isi retine graful printr-un vector de muchii (vectorul <tex>E</tex>). O muchie este retinuta ca un triplet <tex>(x,y,z)</tex> cu semnficiatie ca muchia porneste de la <tex>x</tex> la <tex>y</tex> si are costul <tex>z</tex>. Dar cel mai rau probabil este faptul ca programul este LENT !

Pentru ca vrem ca prietenul nostru cu copite sa plece cu o parere buna despre informatica, am vrea sa ia 100 de puncte cu aceasta sursa, ba chiar sa ruleze cat mai repede. Este clar ca numarul de iteratii ale _while()-ului_ este influentat direct de ordinea muchiilor in vectorul de muchii <tex>E</tex>.

h2. Date de intrare
În fişierul de intrare $algoritm.in$ se va gasi pe prima linie <tex>T</tex>, numarul de teste.

Fiecare dintre cele T teste are formatul urmator: pe prima linie sunt doua numere <tex>N</tex> si <tex>M</tex>, numarul de noduri, respectiv numarul de muchii din graf. Urmeaza M linii ce descriu muchiile, fiecare continand exact 3 numere <tex>a</tex>, <tex>b</tex>, <tex>c</tex>, cu semnificatia ca exista o muchie de la nodul <tex>a</tex> la nodul <tex>b</tex> care are costul <tex>c</tex>.

Fiecare dintre cele <tex>T</tex> teste are formatul urmator: pe prima linie sunt doua numere <tex>N</tex> si <tex>M</tex>, numarul de noduri, respectiv numarul de muchii din graf. Urmeaza M linii ce descriu muchiile, fiecare continand exact 3 numere <tex>a</tex>, <tex>b</tex>, <tex>c</tex>, cu semnificatia ca exista o muchie de la nodul <tex>a</tex> la nodul <tex>b</tex> care are costul <tex>c</tex>.

h2. Date de ieşire

h2. Restricţii si Precizari

* <tex>T</tex> = <tex>5</tex>

* <tex>T</tex> &le; <tex>5</tex>

* <tex>1</tex> &le; <tex>N</tex> &le; <tex>10^5^</tex>
* <tex>1</tex> &le; <tex>M</tex> &le; <tex>2*10^5^</tex>
* <tex>1</tex> &le; costul unei muchii &le; <tex>10^6</tex>

* Se garanteaza ca exista cel putin o muchie care iese din nodul 1
* In programul lui Por Costel, infinit e definit ca fiind mai mare ca orice numar intreg
* Se accepta orice solutie care respecta cerinta

* **Atentie!** Graful poate contine doua muchii de la x la y, sau muchie de la x la x

* **Atentie!** Graful poate contine doua muchii de la <tex>x</tex> la <tex>y</tex>, sau muchie de la <tex>x</tex> la <tex>x</tex>

h2. Exemplu