S - Sklad

Časový limit: 1s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Spoločnosti Predaj A Leasing Motorových Automobilov sa začalo dariť tak dobre, že nemajú kde uskladniť predvádzacie modely a predobjednávky. Preto uvažujú o tom, že postavia nový sklad. Ak postavia sklad pri najväčšej pobočke, tak nebude to férové pre malú vzdialenú pobočku, ktorá bude platiť veľké náklady za presun automobilu do nej. Preto padlo rozhodnutie, aby nový sklad bol postavený pri takej pobočke, od ktorej najvzdialenejšia pobočka je čo najbližšie.

Úloha

Implementujte program, ktorý určí, pri ktorej pobočke vyrastie nový sklad.

Vstup

Prvý riadok obsahuje 2 čísla reprezentujúce pobočiek N (2 ≤ N ≤ 200) a počet ciest medzi nimi M (1 ≤ M ≤ 40 000).

Nasleduje M riadkov obsahujúcich čísla: A B C reprezentujúce cestu z pobočky A do pobočky B dlhú C (0 ≤ C ≤ 100) a platí 0 ≤ A, B ≤ N - 1

Výstup

Výstupom programu je číslo pobočky, pri ktorej vyrastie nový sklad. Ak je viac pobočiek s danou vlastnosťou, potom vráťte tú, ktorá má najnižšie poradové číslo.

Príklad

Vstup:

Výstup:

16 Finále 1