_-Matei Nakayama- Mihai a primit un cactus._

Un cactus este un graf conex neorientat în care fiecare nod face parte din cel mult un ciclu. Se consideră un cactus cu N noduri şi M muchii cu diverse lungimi. Acesta nu conţine bucle (adică muchii între un nod şi el insuşi) sau muchii paralele (adică două sau mai multe muchii între o singură pereche de noduri).

Un cactus este un graf conex neorientat în care fiecare nod face parte din cel mult un ciclu. Se consideră un cactus cu $N$ noduri şi $M$ muchii cu diverse lungimi. Acesta nu conţine bucle (adică muchii între un nod şi el insuşi) sau muchii paralele (adică două sau mai multe muchii între o singură pereche de noduri).

Mihai vrea să elimine muchii din graful cactus, astfel încât să obţină un arbore cât mai uşor. Distanţa dintre două noduri din arbore este egală cu suma lungimilor muchiilor de pe cel mai scurt drum dintre cele două noduri. Greutatea unui arbore este definită ca fiind suma distanţelor dintre oricare două perechi neordonate de noduri distincte - perechea (1, 2) este echivalentă cu perechea (2, 1).

Mihai vrea să elimine muchii din graful cactus, astfel încât să obţină un arbore cât mai uşor. Distanţa dintre două noduri din arbore este egală cu suma lungimilor muchiilor de pe cel mai scurt drum dintre cele două noduri. Greutatea unui arbore este definită ca fiind suma distanţelor dintre oricare două perechi neordonate de noduri distincte - perechea $(1, 2)$ este echivalentă cu perechea $(2, 1)$.

Ajutaţi-l pe Mihai să găsească *greutatea minimă* a unui arbore obţinut prin eliminarea unor muchii din cactus.
h2. Date de intrare

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

Pe prima linie a fişierului de intrare $cactus.in$ se află două numere $N$, reprezentând numărul de noduri din graf, şi $M$, reprezentând numărul de muchii din graf.
Pe fiecare dintre următoarele $M$ linii se află trei numere $x$, $y$ şi $z$, reprezentând o muchie cu lungimea $z$ între nodurile $x$ şi $y$.

h2. Date de ieşire

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

În fişierul de ieşire $cactus.out$ se va afişa un singur număr, reprezentând greutatea minimă a unui arbore ce se poate obţine din cactusul inţial prin eliminarea unor muchii.

h2. Restricţii

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

* $1 ≤ N ≤ 100 000$
* $N - 1 ≤ M ≤ 200 000$
* $0 ≤ z ≤ 1 000 000 000$
* *Se garantează că răspunsul este cel mult $10^18^$.*
 
table(subtasks). |_. # |_. Punctaj |_. Restrcţii |
| 1 | 4 | Graful este un lanţ (nu conţine niciun ciclu şi fiecare nod are grad cel mult $2$). |
| 2 | 6 | Graful este un arbore (nu conţine niciun ciclu). |
| 3 | 12 | $1 ≤ N ≤ 15$ |
| 4 | 25 | $1 ≤ N ≤ 1000$ |
| 5 | 38 | Graful este un ciclu (fiecare nod are grad $2$). |
| 6 | 15 | Restricţiile iniţiale. |
 
 
h2. Exemple
 
table(example). |_. cactus.in |_. cactus.out |_. Explicaţii |
| 6 6
  1 2 8
  1 3 2
  3 2 1
  1 4 3
  4 5 2
  2 6 4
| 80
| Se elimină muchia $(1 2)$.
|
| 12 14
  1 2 7
  2 3 3
  1 3 7
  3 4 2
  4 5 5
  5 6 10
  6 4 3
  4 7 4
  7 8 2
  8 9 5
  9 10 8
  10 11 1
  11 7 9
  10 12 3
| 787
| Se elimină muchiile $(1 2)$, $(5 6)$, $(9 10)$.
|

h2. Exemplu
 
table(example). |_. cactus.in |_. cactus.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

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