Feladatok‎ > ‎

Internethálózat

Egy internetszolgáltató úgy döntött, hogy egy új megyében teszi elérhetővé a szolgáltatásait. Minket bízott meg, hogy kiszámoljuk, ehhez mely települések között érdemes kábelt lefektetnie.

Az előkészületek során felmérte, hogy egy-egy település között mennyire lenne költséges egy közvetlen összeköttetés megvalósítása. A vállalat célja, hogy a lehető legkevesebb forrás ráfordításával elérje, hogy bármely két település között legyen (akár közvetett) összeköttetés.

Bemenet

Az első sorban N és M értéke, ahol N a települések száma, M pedig a lehetséges közvetlen összeköttetések száma. Az ezt követő M sor egy-egy megvalósítható közvetlen összeköttetés adatait tartalmazza 3-3 pozitív egész számmal: az első kettő a két település sorszáma (1 és N között), a 3. szám pedig az összeköttetés megvalósításának költsége.

Kimenet

Egymás alá felsorolva azok az összeköttetések (tetszőleges sorrendben), amiket érdemes megvalósítani. Egy összeköttetést a két végpont település sorszámával jellemzünk.

Példa

Bemenet

6 9
1 2 4
2 3 3
3 4 1
4 5 5
5 1 2
6 1 9
6 3 7
2 5 5
4 2 4

Kimenet

3 4
5 1
2 3
1 2
6 3

Segítség