Cesty v orientovaném acyklickém grafu

Budeme uvažovat grafy, v nichž jsou jak uzly tak hrany ohodnoceny celými čísly.
Uzlová délka cesty v grafu je rovna součtu vah všech uzlů této cesty. Hranová délka cesty v grafu je rovna součtu vah všech hran této cesty. Cestu nazveme hranově přípustnou, pokud v grafu neexistuje žádná jiná cesta s větší hranovou délkou.
Hranově přípustnou cestu v grafu nazveme uzlově optimální, pokud v grafu neexistuje žádná jiná hranově přípustná cesta s větší uzlovou délkou.

     

Obrázek 1. Ilustrace k Příkladům 1, 2, 3 níže. Váhy uzlů jsou vyznačeny na tmavém pozadí. Uzlově optimální cesty vedou: V případě a) uzly 3 − 1 − 0, v případě b) uzly 2 − 0 − 1 − 5 nebo 2 − 3 − 4 − 5 nebo 2 − 6 − 7 − 5, v případě c) uzly 6 − 5 − 7.

Úloha

Určete uzlovou délku a hranovou délku některé uzlově optimální cesty v daném orientovaném acyklickém grafu.

Vstup

První řádek obsahuje dvě celá čísla N, M oddělená mezerou a představující (v tomto pořadí) počet uzlů a hran v daném acyklickém orientovaném grafu. Uzly grafu jsou číslovány 0, 1, ..., N−1. Na druhém řádku jsou ve vzrůstajícím pořadí čísel uzlů uvedeny váhy uzlů. Jednotlivé vahy jsou odděleny mezerami. Následuje M řádků, každý specifikuje jednu hranu grafu. Řádek obsahuje tři celá čísla A, B, C (v tomto pořadí) oddělená mezerou a představující hranu z uzlu A do uzlu B s váhou C.
Platí: 2 ≤ N ≤ 104, 2 ≤ M ≤ 106. Všechny váhy uzlů i hran nepřesáhnou v absolutní hodnotě 103.

Výstup

Výstup obsahuje jeden textový řádek s dvěma celými čísly UD a HD oddělenými mezerou. UD představuje uzlovou délku některé uzlově optimální cesty v daném grafu, HD představuje hranovou délku téže cesty.

Příklad 1

Vstup
4 5
-1 -1 -3 -1
1 0 10
2 1 -5
3 2 -5
3 1 15
2 0 25
Výstup
-3 25
Graf v Příkladu 1 je znázorněn na Obrázku 1a).

Příklad 2

Vstup
8 9
1 6 100 2 5 100 3 4
2 0 20
2 3 30
2 6 10
0 1 30
3 4 10
6 7 20
1 5 10
4 5 20
7 5 30
Výstup
207 60
Graf v Příkladu 2 je znázorněn na Obrázku 1b).

Příklad 3

Vstup
8 8
10 40 90 20 50 90 30 60
0 2 2
2 1 5
3 2 2
2 4 4
3 5 2
5 4 1
6 5 5
5 7 2
Výstup
180 7
Graf v Příkladu 3 je znázorněn na Obrázku 1c).

Veřejná data

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