Úloha: počítačová síť

Ředitelství státní správy jistého nejmenovaného resortu spravuje N budov a chce pro všechny svoje budovy zajistit připojení na Internet. Protože připojení každé budovy zvlášť by se v době úspor a škrtů nepodařilo prosadit, ředitelství rozhodlo, že pouze pro I (1 <= I <= N) budov zakoupí nezávislé vysokorychlostní připojení na Internet. Kromě toho mezi některými dvojicemi budov bude vybudováno propojení optickým kabelem. Za tímto účelem si ředitelství nechalo vypracovat velké množství cenových nabídek od různých firem. Každá nabídka obsahuje cenu za propojení dvojice určitých budov optickým kabelem.

Budova je připojena na Internet pokud je sama připojena nezávislým vysokorychlostním připojením na Internet nebo pokud z této budovy existuje cesta po optickém kabelu do nějaké jiné budovy, která již na Internet připojena je.

Úloha:

Pro známé N, I a všechny cenové nabídky napište efektivní algoritmus, jenž určí, kterým I budovám se má zakoupit nezávislé připojení na Internet a které dvojice budov se mají propojit optickým kabelem tak, aby se z každé budovy bylo možné připojit na Internet a přitom, aby celková cena vybudovaných optických kabelů byla co nejmenší (Cena za nezávislé připojení libovolných I budov na Internet je vždy stejná, a proto ji nemá smysl uvažovat.). Dvojice budov, které je potřeba propojit seřadte vzestupně podle ceny spoje a nejnižšího čísla budovy (v případe rovnosti ceny), pro každý spoj uveďte jako první budovu s nižším číslem. Budovy jsou číslovány od 1 do N.

Vstup:

Ve vstupním souboru je na prvním řádku uveden počet budov N, na druhém řádku počet nezávislých připojení na Internet I a na každém dalším řádku je jedna cenová nabídka představovaná třemi celými kladnými čísly (číslo výchozí budovy, číslo cílové budovy a cena realizace) oddělenými mezerami. Poslední řádek obsahuje tři nuly (oddělené mezerami).

Výstup:

Pokud připojení k Internetu pro všechny budovy není možné realizovat, je výstupem programu jediný řádek s -1. Jinak je na prvním řádku celková cena připojení k Internetu. Na druhém řádku je vypsáno I čísel budov oddělených mezerami, které budou nezávisle připojeny k Internetu. Na dalších řádcích jsou vypsaná všechna nutná přímá propojení optickým kabelem jako trojice (formát viz vstup) pro připojení k Internetu. Výstup je ukončen trojicí s nulami (stejně jako ve vstupním souboru).

Příklad:

Vstupní soubor:

 
5
2
1 2 100
1 3 10
1 4 100
1 5 300
3 1 10
2 3 100
2 4 10
2 5 300
3 4 47
3 5 27
1 3 56
4 5 74
2 1 100
0 0 0

Výstupní soubor:

 
47
1 2
1 3 10
2 4 10
3 5 27
0 0 0