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

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 <tex>M</tex> 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