Cykl

Limit pamięci: 32 MB

Masz podany skierowany graf z wagami na krawędziach. Twoim zadaniem jest znalezienie cyklu w tym grafie o jak największej średniej wadze krawędzi.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite (), oznaczające odpowiednio liczbę wierzchołków oraz krawędzi grafu. W kolejnych wierszach znajduje się opis kolejnych krawędzi w postaci trzech liczb (). Oznacza to że istnieje krawędź z wierzchołka do wierzchołka o wadze krawędzi . Między każdą parą wierzchołków będzie istniała co najwyżej jedna krawędź w każdą stronę.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znajdować jedna liczba rzeczywista, równa maksymalnej średniej wadze cyklu w podanym grafie. Liczba ta powinna być zapisana z dokładnością do 4 miejsc po przecinku. Możesz założyć że w grafie zawsze będzie istniał jakiś cykl.

Przykład

Dla danych wejściowych:

5 6
1 2 6
2 3 2
3 1 3
2 4 1
4 2 5
5 4 100

poprawną odpowiedzią jest:

3.6667

Autor zadania: Adrian Jaskółka (zapożyczenie).