Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Kunnostus

Kunnostus


View task | Model solution | Statistics


Kunnostus

Time limit:1.00 s
Memory limit:128 MB

Bittimaassa on $n$ kaupunkia, joiden välillä on $m$ tietä. Tällä hetkellä teiden kunto on kuitenkin niin huono, ettei niitä voi käyttää. Tehtäväsi on kunnostaa osa teistä niin, että mistä tahansa kaupungista pääsee mihin tahansa kaupunkiin.

Tiedät jokaisesta tiestä, paljonko sen kunnostaminen maksaa, ja sinun tulee valita kunnostettavat tiet niin, että kokonaiskustannus on mahdollisimman pieni.

Syöte

Syötteen alussa on kaksi kokonaislukua $n$ ja $m$: kaupunkien määrä ja teiden määrä. Kaupungit on numeroitu $1,2,\ldots,n$.

Sitten syötteessä on $m$ riviä, joista jokainen kuvaa yhden tien. Rivillä on kolme kokonaislukua $a$, $b$ ja $c$: kaupunkien $a$ ja $b$ välillä on tie, jonka kunnostus maksaa $c$. Kaikki tiet ovat kaksisuuntaisia.

Tuloste

Tulosta yksi kokonaisluku: paljonko teiden kunnostus maksaa yhteensä. Kuitenkin jos tehtävä ei ole mahdollinen, tulosta QAQ.

Rajat
Esimerkki

Syöte:
5 6
1 2 3
2 3 5
2 4 2
3 4 8
5 1 7
5 4 4


Tuloste:
14