Úloha: Výstavba potrubní pošty

Velká nadnárodní firma se rozhodla ve své centrále vybudovat potrubní poštu, která by umožnila rozesílání poštovních zásilek z oddělení příjmu pošty do všech kanceláří. Za tímto účelem si firma nechala vypracovat cenové nabídky na jednosměrné propojení dvojic kanceláří. Jednosměrné propojení dvojice různých kanceláří může mít více různých cenových návrhů, ale pro některé dvojice kanceláří nemusí cenová nabídka na jednosměrné propojení existovat (takové propojení je potom nerealizovatelné). Navíc jsou některá spojení z historických důvodů již vybudovaná.

Nyní firma potřebuje rozhodnout, která kancelář by byla nejvhodnější pro funkci oddělení příjmu pošty, a jaké propojení jednotlivých kanceláří z možných cenových nabídek realizuje při splnění následujících požadavků:

1. Z oddělení příjmu pošty musí existovat buď přímé nebo nepřímé spojení do všech kanceláří v centrále. Přímým spojením se myslí jednosměrné propojení dvou kanceláří, na které existuje cenová nabídka. Nepřímým spojením rozumíme několik přímých na sebe navazujících spojení dvojic kanceláří tak, abychom mohli doručit zásilku ze zdrojové do cílové kanceláře.
2. Cena vybudování potrubní pošty musí být co nejnižší. Cenou potrubní pošty přitom rozumíme součet cen všech jednosměrných propojení, které je potřeba vybudovat pro správné fungování pošty dle požadavků firmy.
3. Pokud existuje více řešení za stejnou cenu, je dalším kritériem co nejnižší počet nových jednosměrných propojení, které je třeba vybudovat. Pokud je takových řešení více, pak jsou mezi sebou rovnocenné a tudíž všechny správné.

Napište program, který zjistí, zda je na základě vstupních údajů možné vybudovat potrubní poštu dle požadavků firmy. Pokud ano, program určí celkovou cenu potrubní pošty, dále kancelář, která bude mít funkci oddělení příjmu pošty, a konečně jaká propojení z nabídnutých cenových návrhů budou muset být realizována.

Vstup:

Ve vstupním souboru je na prvním řádku uveden počet kanceláří a na každém dalším řádku je jeden cenový návrh (nebo již realizované spojení) představovaný třemi celými čísly (číslo výchozí kanceláře, číslo cílové kanceláře a cena realizace) oddělenými mezerami. Čísla určující výchozí a cílovou kancelář jsou nezáporná. Pokud je spojení již vybudované, je cena realizace -1, jinak je cena realizace nezáporná. Poslední řádek obsahuje tři nuly (oddělené mezerami).

Výstup:

Pokud poštu není možné realizovat, je výstupem programu jediný řádek s -1. Jinak je na prvním řádku celková cena pošty. Na druhém řádku je číslo kanceláře, která bude mít funkci oddělení příjmu. Na dalších řádcích jsou vypsaná všechna nutná přímá spojení (jak ta, která jsou již vybudovaná, tak i ta, která je potřeba ještě vybudovat) jako trojice (formát viz vstup) pro realizaci pošty. Na pořadí řádků s trojicemi nezáleží. Výstup je ukončen trojicí s nulami (stejně jako ve vstupním souboru). Vypisovaní nadbytečných přímých spojení, byť by se nezvýšila cena realizace, není povoleno.

Nápověda:

K efektivní realizaci úlohy doporučujeme prostudovat původní Tarjanův algoritmus v článku zde a Carmeriniho opravu chyb z Tarjanova článku v článku zde.

Příklad 1:

7
0 1 -1
0 1 0
0 2 60
1 3 -1
2 3 1
3 5 1000
0 4 2
3 0 -1
0 3 30
0 3 300
5 6 0
6 3 950
0 0 0

1003
2
2 3 1
3 0 -1
0 1 -1
3 5 1000
5 6 0
0 4 2
0 0 0