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

Se consideră $N$ puncte strategice aflate în administrarea Ministerului Apărării (MA). Pentru fiecare pereche de puncte se cunoaşte costul de conectare directă, în caz că se doreşte realizarea conectării directe a punctelor din acea pereche.
 
# Să se aleagă un număr de perechi de noduri a căror conectare va fi efectiv implementată astfel încât, la finalul lucrării, între oricare dintre cele $N$ noduri să existe comunicare directă sau indirectă prin conexiunile realizate şi, în plus, costul total al lucrărilor să fie minim.

Se consideră $N$ puncte strategice aflate în administrarea Ministerului Apărării (MA). Pentru $M$ perechi de puncte se cunoaşte costul de conectare directă, în caz că se doreşte realizarea conectării directe a punctelor din acea pereche.
# Să se aleagă un număr de perechi de noduri a căror conectare va fi efectiv implementată, dintre cele $M$, astfel încât, la finalul lucrării, între oricare dintre cele $N$ noduri să existe comunicare directă sau indirectă prin conexiunile realizate şi, în plus, costul total al lucrărilor să fie minim (se garantează că acest lucru este întotdeauna posibil).

# Comandamentul Trupelor de Uscat (CTU) va prelua $5$ dintre cele $N$ noduri, astfel încât, conform strategiei de conectare stabilită la (1), comunicarea între oricare dintre cele $5$ noduri să se realizeze fie direct, fie folosind numai puncte preluate de CTU. Ştiind că toate costurile de conectare (stabilite la (1)) dintre cele $5$ puncte vor fi plătite de CTU, să se aleagă convenabil cele $5$ noduri astfel încât costul conectărilor (de la (1)) rămase în responsabilitatea MA să fie minim.
h2. Date de intrare

Fişierul de intrare $aparare.in$ conţine pe prima linie valoarea lui $N$, numărul de puncte strategice şi pe următoarele $N - 1$ linii, valori reprezentând costurile de conectare dintre puncte. Astfel, pe fiecare linie $i$ din fişier ($i > 1$) se află $i - 1$ valori reprezentând costurile de conectare dintre nodul $i$ şi nodurile $1, 2, ..., i - 1$.

Fişierul de intrare $aparare.in$ conţine pe prima linie valoarea lui $N$, numărul de puncte strategice, urmată de valoarea lui $M$, numărul de perechi de puncte strategice pentru care se ştie costul de conectare directă. Pe fiecare din următoarele $M$ linii, se găsesc câte $3$ numere: $i$, $j$ şi $c$ ({$1 &le; i < j &le; N$}) separate printr-un spaţiu, cu semnificaţia că pentru a conecta direct punctele $x$ şi $y$ trebuie plătit costul $c$.

h2. Date de ieşire

h2. Restricţii

* $5 ≤ N ≤ 9999$

* $5 ≤ N ≤ 100 000$
* $2 * N ≤ M ≤ N * (N - 1) / 2$
* $M ≤ 500 000$

* Costurile de conectare sunt numere naturale strict pozitive, *distincte două câte două*, de cel mult $9$ cifre fiecare.
* Costul de conectare de la nodul $i$ la nodul $j$ este acelaşi cu costul de conectare de la nodul $j$ la nodul $i$, oricare ar fi $1 ≤ i, j ≤ N$.

* Se acordă $40%$ din punctaj pentru prima valoare corectă şi $100%$ din punctaj pentru ambele valori corecte.

* Se acordă $40%$ din punctaj pentru prima valoare corectă şi $100%$ din punctaj pentru ambele valori corecte. *Pentru a primi punctaj parţial trebuie să afişaţi ambele valori cerute.*

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

| 6
  5
  3 11
  7 2 1
  6 10 4 14
  9 16 8 20 18

| 6 15
  1 2 5
  1 3 3
  2 3 11
  1 4 7
  2 4 2
  3 4 1
  1 5 6
  2 5 10
  3 5 4
  4 5 14
  1 6 9
  2 6 16
  3 6 8
  4 6 20
  5 6 18

| 18
  2
|
h3. Explicaţie

Se conectează perechile: $3-1$, $3-4$, $3-5$, $3-6$, $2-4$ obţinându-se costul total minim $18$.
Se preiau de către CTU punctele $1$, $3$, $4$, $5$ şi $6$, cu costurile aferente de conectare, MA plătind doar conectarea $2-4$ cu costul $2$.

Se conectează perechile: $1 - 3$, $3 - 4$, $3 - 5$, $3 - 6$, $2 - 4$ obţinându-se costul total minim $18$.
Se preiau de către CTU punctele $1$, $3$, $4$, $5$ şi $6$, cu costurile aferente de conectare, MA plătind doar conectarea $2 - 4$ cu costul $2$.

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