| 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.
Kaupungista ei voi olla tietä itseensä, ja jokaisen kahden kaupungin välillä on enintään yksi tie.
Tuloste
Tulosta yksi kokonaisluku: paljonko teiden kunnostus maksaa yhteensä. Kuitenkin jos tehtävä ei ole mahdollinen, tulosta QAQ.
Rajat
- $1 \le n \le 10^5$
- $1 \le m \le 2 \cdot 10^5$
- $1 \le a,b \le n$
- $1 \le c \le 10^9$
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
