Dlouhé sjezdovky

Organizátoři lyžařského kursu si hodlají předplatit na týden využívání jedné sjezdovky v blízké horské oblasti, kde budou účastníci intenzivně trénovat. Sjezdovek je v oblasti více a bude třeba vybrat některou vhodnou. Ukázalo se, že výpravy se zúčastní také významná skupina začínajících běžkařů, která bude pro trénink potřebovat co nejmírnější svahy. Aby se výprava držela během dne pokud možno pohromadě, navrhují organizátoři následující řešení. Sjezdovka bude vybrána tak, aby z jejího horního konce vedla do jejího dolního konce ještě jiná trasa využívající další sjezdovky. Na této trase budou trénovat běžkaři. Délka této trasy by měla být co největší, čímž se zajistí mírné klesání a příležitost pro výcvik.

Situace v oblasti je popsána takto: Každá sjezdovka má stanici lanovky na svém horním i na svém dolním konci, žádná stanice nestojí jinde než na horním nebo na dolním konci některé sjezdovky. Dvě sjezdovky na sebe navazují, pokud dolní stanice první sjezdovky je zároveň horní stanicí druhé sjezdovky. Kvalita sjezdovky je délka nejdelší trasy, která vede z její horní stanice do její dolní stanice. Tato nejdelší trasa může být buď samotná sjezdovka nebo posloupnost jiných na sebe navazující sjezdovek. Délka trasy je rovna součtu délek sjezdovek na trase. Sjezdovka je optimální, pokud žádná jiná sjezdovka v oblasti nemá větší kvalitu.
Předpokládáme, že každá sjezdovka vede s kopce, na žádné trase se tedy nelze vrátit do některé předchozí stanice na této trase

     


Obrázek 1. Schéma sjezdovek v oblasti. Optimální sjezdovky jsou vyznačeny tmavě a vedou mezi dvojicemi stanic (0, 1), (1, 10), (2, 10), (5, 11). Nejdelší trasy příslušející jednotlivým optimálním sjezdovkám jsou vyznačeny přerušovaně, všechny mají délku 14.

Úloha

K dispozici je úplný plán sjezdovek v dané oblasti včetně jejich délek a stanic na jejich koncích. Vypište seznam všech optimálních sjezdovek.


Vstup

První řádek obsahuje dvě celá kladná čísla N, M oddělená mezerou představující po řadě počet stanic a počet sjezdovek. Stanice jsou očíslovány od 0 do N−1 tak, že stanice ve větší nadmořské výšce má vždy nižší číslo než stanice v menší nadmořské výšce.
Za prvním řádkem následuje M řádků, každý představuje jednu sjezdovku. Na řádku jsou uvedena tři celá čísla oddělená mezerami. První představuje číslo horní stanice sjezdovky, druhé představuje číslo dolní stanice sjezdovky a třetí představuje délku sjezdovky. Sejzdovky jsou v seznamu uvedeny v libovolném pořadí.
Hodnota N nepřesáhne 5000.

Výstup

Výstup obsahuje seznam všech optimálních sjezdovek. Každý řádek obsahuje číslo horní a dolní stanice jedné optimální sjezdovky, čísla jsou oddělena mezerou. Řádky jsou uspořádány v rostoucím lexikografickém pořadí. Počet řádků na výstupu nepřesáhne 10.

Příklad 1

Vstup
13 21
3 5 1
5 11 12
5 8 5
8 11 8
2 3 4
2 5 6
5 7 3
7 8 2
7 11 11
2 7 8
7 9 3
2 4 5
4 9 4
2 10 10
4 10 7
9 10 2
0 1 14
1 10 4
1 6 5
6 10 9
6 12 6
Data a řešení příkladu 1 jsou znázorněna na obrázku 1.

Příklad 2

Vstup
6 7
0 1 4
0 5 7
1 5 5
3 5 7
2 5 5
4 5 9
2 3 2
Výstup
0 5
2 5
4 5

Příklad 3

Vstup
10 13
7 9 10
8 9 10
7 8 1
5 6 4
3 6 8
4 5 5
2 5 7
0 2 5
2 4 6
0 4 4
3 4 2
1 3 9
1 4 4
Výstup
0 4
1 4
2 5
3 6
7 9

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