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

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

Se da un graf bidirectionat $G$ cu $N$ noduri si $M$ muchii cu cost. Se cere sa se aleaga o submultime de muchii dintre aceste $M$, de cost minim, astfel incat sa existe un singur drum intre oricare doua noduri parcurgand doar muchii din submultimea aleasa.

Poveste şi cerinţă...

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

Fişierul de intrare $apm.in$ ...

h2. Date de ieşire

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

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

h2. Restricţii

* $1 ≤ N ≤ 200.000$
* $1 ≤ M ≤ 200.000$
* Pentru $20%$ din teste $N,M ≤ 20$
* Pentru inca $30%$ din teste $N,M ≤ 5.000$
* Intre oricare doua noduri va exista decat o muchie.

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

h2. Exemplu
table(example). |_. apm.in |_. apm.out |

| 9 14
1 2 10
1 3 -11
2 4 11
2 5 11
5 6 13
3 4 10
4 6 12
4 7 5
3 7 4
3 8 5
8 7 5
8 9 4
9 7 3
6 7 11
| 37

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

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$. Tin sa mentionez ca solutia nu este unica.

...

h2. Indicaţii de rezolvare
 
 
h2. Aplicatii
 
 
== include(page="template/taskfooter" task_id="inversmodular") ==

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

public

task: apm