Asfaltové silnice

Ve státě Ubanangwo panují neutěšené poměry, všechny silnice jsou hliněné. Vláda se rozhodla silnice vyasfaltovat, aby všechna městečka a vesnice ve státě (velká města tam stejně nemají) byla propojena vyasfaltovanou cestou. Na stole má dva projekty.

První projekt je jednoduchý. Navrhuje, aby se za co nejnižší celkovou cenu vyasfaltovaly v celém státě pouze některé silnice, a to tak, že pak bude možné cestovat po asfaltu mezi libovolnými dvěma vesničkami/městečky, přestože to mnohdy nebude cesta nejkratší.

Proti prvnímu projektu mají výhrady mnozí kmenoví náčelnící. Argumentují, že se takto snadno stane, že asfaltované spojení mezi osadami jednoho kmene povede částečně mimo území kmene, případně i přes území více jiných kmenů. Náčelnící proto připravili alternativní dvoufázový projekt. Ten navrhuje, aby se v první fázi propojily mezi sebou osady uvnitř území každého kmene s použitím stejné strategie jako v prvním projektu, to jest, že výstavba propojení uvnitř území každého kmene bude co nejlacinější. Pak sice stále cestování po asfaltu mezi osadami jednoho kmene nebude nejkratší, ale povede vždy jen přes území tohoto kmene. Ve druhé fázi projektu se pak vyberou ty silnice mimo jednotlivá kmenová území, jejichž vyasfaltování zaručí propojení všech osad ve státě nejlevnějším způsobem.

O silnici se v tomto kontextu říká, že leží na území určitého kmene pouze a jen tehdy, pokud obě osady, které spojuje, leží na území tohoto kmene, jinak se o ní řiká, že leží mimo kmenová území.

Ve státě jsou kromě kmenových také další osady, které postavili přistěhovalci. Ty jsou ve státní správě a pravomoc kmenových náčelníků se na ně nevztahuje. Stejně jako ostatní kmenové osady musí být tyto státní osady součástí výsledné asfaltované sítě. Silnice, která spojuje státní osadu s jakoukoli jinou osadou, ať státní nebo kmenovou, je považována při výstavbě za silnici mimo kmenová území.

Vláda nyní potřebuje znát cenu obou projektů, aby mohla dále konstruktivně jednat s kmenovými náčelníky. Má k dispozici seznam všech osad, kmenových i přistěhovaleckých, a také seznam všech silnic mezi osadami. U každé silnice zná cenu za její případné vyasfaltování.

Vstup

Na vstupu je nejprve řádek se dvěma čísly n a k oddělenými mezerou. Hodnota n udává počet osad ve státě a hodnota k udává počet kmenů ve státě. Osady jsou očíslovány 0, 1, ..., n−1. Kmeny jsou označeny čísly 1, 2, ..., k. Přistěhovalecké osady jsou označeny hodnotou 0.
Následuje seznam osad v libovolném pořadí. Každá položka seznamu je na jednom řádku a obsahuje dvě čísla oddělená mezerou. První je číslo osady, druhé je číslo kmene, jemuž osada náleží, nebo 0, pokud jde o přistěhovaleckou osadu.
Za seznamem osad následuje seznam silnic s cenami za jejich asfaltování. Každá silnice je zapsána na jednom řádku, obsahujícím tři celá čísla oddělená mezerou. První dvě čísla označují (v libovolném pořadí) dvě osady spojené touto silnicí a třetí představuje nezápornou cenu za její vyasfaltování. Seznam silnic je ukončen řádkem obsahujícím tři nuly oddělené mezerami.
Existence řešení podle prvního i podle druhého projektu je zaručena. Vstup neobsahuje prázdné řádky. Množina přistěhovaleckých osad může být prázdná, množina osad každého kmene je neprázdná, může však obsahovat jen jedinou osadu. Počet osad nepřevýší 1200, počet kmenů nepřevýší 100, počet silnic nepřevýší 10000. Mezi každými dvěma osadami jednoho kmene je vždy možné cestovat po silnicích bez nutnosti návštěvy osady jiného kmene nebo osady přistěhovalecké. Nenastává případ, že by některé dvě osady bylz přímo spojeny více než jednou silnicí, to jest žádné dvě silnice nespojují bezprostředně dvě stejné osady.

Výstup

Na výstupu je řádek se dvěma celými čísly oddělenými mezerou. První číslo představuje cenu prvního projektu, druhé číslo cenu druhého projektu.

Příklad 1

Vstup:

8 2
0 1
3 1
5 1
1 0 
2 2
4 2
7 2
6 0
3 0 30
0 1 10
1 2 6
2 4 30
4 7 5
7 6 10
6 5 4
5 3 5
0 5 40
1 6 5
2 7 40
0 0 0

Výstup:

45 85

Ilustrace příkladu 1: Na prvním řádku obrázku je uvedena sliniční síť, druh osad je vyznačen na šedém podkladu. Následuje řešení podle prvního projektu. Druhý řádek obrázku znázorňuje řešení v obou fázích druhého projektu.

Příklad 2

Vstup:

6 2
0 1
1 2
2 1
3 1
4 1
5 2 
1 0 30
3 0 40
2 0 20
2 3 5
2 4 5
3 4 10
4 5 50
5 1 3000
0 0 0

Výstup:

110 3060 

Schéma osad a cen za asfaltování v příkladu 2.

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data