- Time limit: 1.00 s
- Memory limit: 128 MB
Bittimaassa on kaupunkia, joiden välillä on 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 ja : kaupunkien määrä ja teiden määrä. Kaupungit on numeroitu .
Sitten syötteessä on riviä, joista jokainen kuvaa yhden tien. Rivillä on kolme kokonaislukua , ja : kaupunkien ja välillä on tie, jonka kunnostus maksaa . 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
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