O - Potraviny

Časový limit: 2s, 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 ]

Vedenie Potravín ALMA sa rozhodlo expandovať. Chcú postaviť nové pobočky do niekoľkých obcí tak, aby obyvatelia okolitých obcí mali potraviny čo najbližšie (najvzdialenejšia obec od jej najbližšej pobočky je najmenšia možná).

Úloha

Implementujte program, ktorý určí, do ktorých obcí sa najviac oplatí postaviť pobočky.

Vstup

Prvý riadok obsahuje 3 čísla reprezentujúce počet obcí N (2 ≤ N ≤ 50) nepokrytých Potravinami ALMA, počet ciest medzi obcami M (1 ≤ M ≤ 150) a počet nových plánovaných pobočiek P (2 ≤ P ≤ 10).

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

Výstup

Výstupom programu je P medzerou oddelených čísel obcí, do ktorých sa najviac oplatí postaviť nové pobočky. Ak je takých kombinácií viac, vráťte najmenšiu rastúcu postupnosť čísel obcí.

Príklad

Vstup:

Výstup:

1 3

16 Finále 2