In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
Psst... Ruszyły zawody olimpiady informatycznej dla uczniów szkół podstawowych i średnich. Zadania na tych konkursach są bardzo podobne do zadań, które rozwiązujesz, tutaj, na Szkopule. Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Matrix
Limit pamięci: 256 MB
Wyrocznia zaczęła aktualizować dane i cały Matrix zaczął lagować. Traf chciał, że akurat wtedy Neo wykonywał niezwykle poważną misję.
Misja wymaga, aby mógł on się szybko przemieszczać pomiędzy wybranymi k budkami telefonicznymi. Na szczęście lagi nie pojawiają
się od razu w całym Matrixie, lecz stopniowo.
Miasto, w którym Neo wykonuje misję składa się z n skrzyżowań połączonymi m drogami. Na niektórych ze skrzyżowań stoją budki
telefoniczne. Lagi pojawiają się z czasem na kolejnych ulicach. Neo nie chce przemiaszczać się po już zlagowanych (po co mu latanie,
skoro lagi). Nie chce on także latać nad, przez i pod budynkami, aby nie zwracać zbyt dużej uwagi agentów. Zastanawia się teraz jak
długo może jeszcze wykonywać swoją misję, aby szybko (bez lagów) móc przemieścić między dowolną parą budek telefonicznych.
Wejście
W pierwszej linii wejścia znajdują się liczby n, m i k (1 <= k <= n <= 500 000, 0 <= m <= 1 000 000).
W następnym wierszu znajdują się numery skrzyżowań, na których znajdują się budki telefonizne. W kolejnych m wierszach
są opisy kolejnych ulic w postaci trzech liczb: ai, bi i ti (1 <= ai, bi <= n,
1 <= ti <= 109), co oznacza, że i-ta droga łączy skrzyżowania ai i bi
i zaczyna lagować w ti-ej minucie.
Wyjście
Na wyjście wypisz ostatnią minutę, w jakiej Neo może nadal wykonywać swoją misję. Jeśli nie może jej wykonywać nawet w chwili 0
wypisz -1, natomiast jeśli będzie mógł wykonywać ją zawsze wypisz "KEEP CALM AND FOLLOW THE WHITE RABBIT".