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/
Spacer
Limit pamięci: 256 MB
Las, w którym bajtAlina zbiera maliny składa się z n polan połączonych m jednokierunkowymi ścieżkami. Na niektórych z tych dróg rosną
piękne kwiaty, na innych zaś leżą butelki pozostawione przez GraMbca, a jeszce innymi można trafić do Krainy Grzybów. Z tego powodu
chodzenie jednymi ścieżkami może być bardziej męczące niż innymi (w niektórych przypadkach może być nawet problem z powrotem).
bajtAlina każdej z dróg przypisała liczbę całkowitą z przedziału [-109; 109], oznaczające poziom jej zmęczenia
po przejściu daną ścieżką (liczby ujemne oznaczają, że bajtAlina wypoczywa przechodząc; dodatnia, że okropnie się męczy).
Poziom zmęczenia bajtAliny po wycieczce w lesie to średnia liczb nadanych drogom na trasie spaceru.
bajtAlina chciałaby przejść się po lesie w poszukiwaniu malin. Ustaliła, że jej trasa powinna zaczynać się i kończyć na tej samej polance.
Jaką najmniej męczącą trasę może wybrać?
Wejście
W pierwszej linii wejścia znajdują się dwie liczby całkowite n, m (2 <= n <= 100, 1 <= m <= 10 000) oznaczających liczbę polan
i liczbę dróg w lesie. W kolejnych m wierszach znajdują się opisy kolejnych dróg. Opis drogi składa się z trzech liczb ai,
bi i ci, oznaczających, że i-ta droga prowadzi z polany ai do polany bi
o poziomie zmęczenia ci. Drogi nie przecinają się ze sobą, jednak mogą prowadzić mostami i tunelami.
Wyjście
Na wyjście wypisz pojedynczą liczbę oznaczającą minimalny poziom zmęczenia, jaki może osiągnąć bajtAlina spacerując po lesie.
Wynik zostanie uznany za poprawny, jeśli będzie różnił się od optymalnego o co najwyżej 0.01.