== include(page="template/taskheader" task_id="apm") ==

Se da un graf conex bidirectionat $G$ cu $N$ noduri si $M$ muchii cu cost. Se cere sa se aleaga un subgraf, care cuprinde toate nodurile,formeaza un arbore si acest arbore este de cost minim.

Se da un graf conex neorientat $G$ cu $N$ noduri si $M$ muchii, fiecare muchie avand asociat un cost. Se cere sa se determine un subgraf care cuprinde toate nodurile si o parte din muchii, astfel incat subgraful determinat sa aiba structura de arbore si suma costurilor muchiilor care il formeaza sa fie minim posibila. Subgraful cu proprietatile de mai sus se va numi arbore partial de cost minim pentru graful dat.

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$ randuri se vor gasi muchiile sub forma {$X$},{$Y$},{$C$}, cu semnificatia exista muchie intre $X$ si $Y$ cu costul $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

Fisierul de iesire $apm.out$ va contine pe prima linie costul total minim.

Fisierul de iesire $apm.out$ va contine pe prima linie costul arborelui partial de cost minim.

h2. Restricţii