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é).

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ů:

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 spojení dvojic kanceláří tak, abychom mohli doručit zásilku ze zdrojové do cílové kanceláře. 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í potřebných pro správné fungování pošty dle požadavků firmy. 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.

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 představovaný třemi celými kladnými čísly (číslo výchozí kanceláře, číslo cílové kanceláře a cena realizace) oddělenými mezerami. Poslední řádek obsahuje tři nuly (oddělené mezerami).

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í 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).