시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB6000.000%

문제

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.

입력

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

출력

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.

예제 입력 1

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

예제 출력 1

3.6667