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.
polski
