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

Poveste şi cerinţă...

Cristinel si Alex au gasit un grafuri cu N noduri si M muchii. Pe fiecare dintre muchii si noduri era scris un numar.
Vazand aceasta capodopera a matematicii discrete, Alex a propus sa se joace un joc pe acel graf.
Jocul se joaca alternativ, fiecare trebuie sa aleaga un nod care nu a mai fost ales pana se termina graful.
La final, punctajul fiecarui jucator este suma numerelor de pe nodurile alese si a muchiilor
a caror varfuri sunt in multimea nodurilor alese de acel jucator. Formal, scorul unui jucator este
sum(S) + sum(u_i, v_i) daca u_i \in S si v_i \in S. Unde S este multimea nodurilor alese de un jucator.
Care este diferenta dintre scorul lui Alex si a lui Cristinel, daca ambii jucatori joaca optim si Alex incepe primul?

h2. Date de intrare

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

Fişierul de intrare $jocgraf.in$ contine pe prima linie numarul de teste *T*. Urmeaza apoi descrierea fiecarui test care incepe cu *N* si *M*, numarul de noduri si respectiv muchii a grafului. Pe urmatoare linie sunt numerele scrise pe fiecare nod $x_1, x_2, ..., x_N$. Pe urmatoarele *M* linii sunt descrise muchiile ca un triplet *u*, *v*, *numarul de pe muchie*.

h2. Date de ieşire

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

În fişierul de ieşire $jocgraf.out$ va contine *T* linii cu raspunsul corect (sunt sigur de asta) pentru fiecare dintre cele *T* teste.

h2. Restricţii