Sötét utcák

Nehéz időket élünk manapság gazdaságilag, még Bájtföldön is. A működési költségek csökkentése érdekében Bájtföld kormánya úgy döntött, hogy optimalizálja az utcai világítást. Ezidáig minden utca egész éjjel ki volt világítva, amely naponta és méterenként 1 bájtföldi dollárba került. Hogy pénzt takarítsanak meg, úgy döntöttek, hogy ezután nem világítanak ki minden utcát, hanem lekapcsolják a világítást bizonyos utcákban. Hogy Bájtföld lakói továbbra is biztonságban érezzék magukat, úgy akarják optimalizálni a világítást, hogy miután elsötétítenek éjszakára néhány utcát, még mindig maradjon legalább egy kivilágított útvonal Bájtföld minden kereszteződéséből minden másik kereszteződésébe.

Mekkora az a maximális összeg, amelyet Bájtföld kormánya naponta meg tud takarítani anélkül, hogy a lakói veszélyben éreznék magukat?

A bemenet specifikációja

A bemenet számos tesztesetet tartalmaz. Minden teszteset két számmal, m-mel és n-nel kezdődik, amelyek rendre Bájtföld kereszteződéseinek és útjainak a számát jelölik. A bemenetet az m = n = 0 eset zárja. Minden más esetben 1 ≤ m ≤ 200 000 és m – 1 ≤ n ≤ 200 000. Ezután n darab x, y, z számhármas következik, amelyek azt jelentik, hogy x és y között létezik egy z méter hosszú kétirányú utca (0 ≤ x, y < m és x ≠ y). Minden teszteset összefüggő gráfot ír le. Az utcák összhosszúsága minden tesztesetben kisebb, mint 2³¹.

A kimenet specifikációja

Minden tesztesetre egy sort kell a kimenetre írni, amely azt a maximális összeget tartalmazza, amennyit a kormány egy nap alatt meg tud takarítani.

Példa bemenet

1. 7 11
2. 0 1 7
3. 0 3 5
4. 1 2 8
5. 1 3 9
6. 1 4 7
7. 2 4 5
8. 3 4 15
9. 3 5 6
10. 4 5 8
11. 4 6 9
12. 5 6 11
13. 0 0

letöltés szöveges állományként

A példa bemenethez tartozó kimenet

1. 51

letöltés szöveges állományként