Fişierul intrare/ieşire:	aparare.in, aparare.out	Sursă	Tabăra ICHB 2012, Ziua 2, Grupa 2
Autor	Rodica Pintea	Adăugată de	Dan-Constantin Spatarel •spatarel
Timp execuţie pe test	0.625 sec	Limită de memorie	36864 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Aparare

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.

1. 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).
2. 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.

Date de intrare

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 ≤ i < j ≤ N) separate printr-un spaţiu, cu semnificaţia că pentru a conecta direct punctele x şi y trebuie plătit costul c.

Date de ieşire

În fişierul de ieşire aparare.out va conţine pe prima linie un număr natural reprezentând costul total de conectare de la (1), iar pe linia a doua costul total rămas după preluarea de către CTU a celor 5 puncte strategice alese convenabil.

Restricţii

• 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. Pentru a primi punctaj parţial trebuie să afişaţi ambele valori cerute.

Exemplu

Explicaţie

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.

Cum se trimit solutii?