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

Fie un graf $G$ cu $N$ noduri si $N$ muchii, fiecare nod avand un cost asociat. Numim *acoperire* a grafului $G$ o submultime de noduri a sa, $S$, cu proprietatea ca oricum am selecta o muchie din cele $N$, aceasta are cel putin unul din capetele sale in multimea $S$. Costul unei *acoperiri* este dat de suma costurilor nodurilor incluse in *acoperire*.
 
Se cere costul minim al unei acoperiri pentru graful $G$.

Vi se da un graf *conex* neorientat cu $N$ noduri si $N$ muchii, fiecare nod avand un cost. Vi se cere sa gasiti o submultime de noduri de cost minim astfel incat fiecare muchie din graf sa aiba incident cel putin un nod din submultime. Costul unei submultimi se defineste ca fiind suma costurilor fiecarui nod din submultime.

h2. Date de intrare

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

Fişierul de intrare $mvc.in$ va contine pe prima linie un singur numar intreg $N$, reprezentand atat numarul de noduri, cat si numarul de muchii. A doua linie va contine exact $N$ valori, mai exact costurile nodurilor $1$, $2$ ... $N$.
Urmatoarele $N$ linii vor contine fiecare cate $2$ valori, $x$, $y$ cu semnficatia ca exista muchie (neorientata) de la $x$ la $y$.
 

h2. Date de ieşire

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

În fişierul de ieşire $mvc.out$ trebuie sa se afle un singur numar intreg reprezentand costul minim al unei submultimi astfel incat orice muchie sa fie incidenta la cel putin un nod din acea submultime.

h2. Restricţii

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

* $1 ≤ N ≤ 100.000$
* $0 ≤ costul unui nod ≤ 10.000$

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

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

| 5
0 9 1 2 0
5 4
2 1
1 3
3 4
4 2
|2

|
h3. Explicaţie

...
 

Se aleg nodurile $1$ si $4$. Observam ca toate muchiile au exact un capat in submultimea ${1, 4}$. Observam ca si submultimea ${1, 4, 5}$ este tot corecta, si are tot costul 2.

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