h2. Date de intrare

Fisierul de intrare $apm.in$ va contine pe prima linie numerele $N$ si $M$, separate printr-un spatiu. Pe urmatoarele $M$ linii se vor gasi muchiile grafului sub forma {$X Y C$}, cu semnificatia ca exista muchie neorientata intre $X$ si $Y$ de cost $C$.$

Fisierul de intrare $apm.in$ va contine pe prima linie numerele $N$ si $M$, separate printr-un spatiu. Pe urmatoarele $M$ linii se vor gasi muchiile grafului sub forma {$X Y C$}, cu semnificatia ca exista muchie neorientata intre $X$ si $Y$ de cost $C$.

h2. Date de ieşire

h3. Explicatii

_Exemplul 1_:O solutie este sa se pastreze muchiile intre nodurile $7$ si $3$ cu costul {$4$},{$7$} si $4$ cu costul {$5$},{$7$} si $9$ cu costul {$3$},{$7$} si $6$ cu costul {$11$},{$9$} si $8$ cu costul {$4$},{$3$} si $1$ cu costul {$-11$},{$1$} si $2$ cu costul {$10$},{$2$} si $5$ cu costul {$11$}. Insumand costul $37$. Solutia nu este neaparat unica.

_Exemplul 1_: Un arbore partial de cost minim pentru graful dat poate fi format din urmatoarele muchii: ({$7, 3$}), ({$7, 4$}), ({$7, 9$}), ({$7, 6$}), ({$9, 8$}), ({$1, 3$}), ({$1, 2$}) si ({$2, 5$}). Suma costurilor acestor muchii este $37$. Solutia nu este neaparat unica.

_Exemplul 2_:Desi ar parea convenabil sa se introduca toate 3 muchiile, daca am face asta ar exista un ciclu si nu ar fi unic drumul dintre noduri.

_Exemplul 2_: Desi solutia optima ar parea la prima vedere introducerea tuturor celor 3 muchii, acest lucru nu este posibil deoarece s-ar crea un ciclu. Vor fi selectate muchiile {$(2, 3)$} si {$(3, 1)$}.

h2. Indicaţii de rezolvare