Grămezi

Problema

Într-un oraș, există $n$ intersecții conectate prin $m$ drumuri bidirecționale. Fiecare drum are o lungime asociată. Se dorește să se construiască un sistem de transport public eficient care să conecteze toate intersecțiile, minimizând costul total al drumurilor utilizate.

Mai precis, trebuie să găsiți un subgraf al rețelei de drumuri care să fie un arbore acoperitor minim (MST) al grafului inițial. Un arbore acoperitor minim este un subgraf care conectează toate nodurile (intersecțiile) și are suma lungimilor drumurilor minimă posibilă.

Intrare

• Prima linie conține două numere întregi $n$ și $m$, reprezentând numărul de intersecții și numărul de drumuri, respectiv.

• Următoarele $m$ linii conțin fiecare câte trei numere întregi $u$, $v$ și $w$, indicând că există un drum între intersecția $u$ și intersecția $v$ cu lungimea $w$.

Ieșire

• Afișați costul total minim al drumurilor din arborele acoperitor minim.

Restricții

• 1 \leq n \leq 1000

• 1 \leq m \leq 100000

• 1 \leq w \leq 1000000

• Graful inițial este conex, adică există cel puțin un drum între orice două intersecții.

Exemplu

Intrare:

4 5
1 2 1
2 3 2
3 4 3
4 1 4
1 3 5

Ieșire:

6

În exemplul de mai sus, arborele acoperitor minim poate fi format din drumurile cu lungimile 1, 2 și 3, având un cost total de 6.