Mineri

Problemă:

Într-un oraș, există $n$ intersecții numerotate de la $1$ la $n$. Unele dintre aceste intersecții sunt conectate prin drumuri bidirecționale. Fiecare drum are o lungime asociată. Orașul dorește să construiască un sistem de transport public care să conecteze toate intersecțiile, minimizând costul total al drumurilor utilizate.

Sarcina ta este să determini costul minim necesar pentru a conecta toate intersecțiile din oraș folosind drumurile existente.

Intrare:

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

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

Ieșire:

• Afișați un singur număr întreg, reprezentând costul minim necesar pentru a conecta toate intersecțiile.

Constrângeri:

• 1 \leq n \leq 1000

• 0 \leq m \leq 10000

• 1 \leq u, v \leq n

• 1 \leq w \leq 1000000

Notă:

Este garantat că există cel puțin o modalitate de a conecta toate intersecțiile.