cactus

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

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 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.

Date de intrare

Pe prima linie a fişierului de intrare se află două număre $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$.

Date de ieșire

În fişierul de ieşire 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.

Restricții și precizări

• $1 \leq N \leq 100\ 000$
• $N-1 \leq M \leq 200\ 000$
• $0 \leq z \leq 1\ 000\ 000\ 000$
• Se garantează că răspunsul este cel mult $10^{18}$.

Exemple

cactus.in

6 6
1 2 8
1 3 2
3 2 1
1 4 3
4 5 2
2 6 4

cactus.out

80

Se elimină muchia $(1, 2)$.

cactus.in

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

cactus.out

787

Se elimină muchiile $(1, 2)$, $(5, 6)$, $(9, 10)$.