Пьяная прогулка
После того как вы немного перебрали с выпивкой вечером, вы оказываетесь на длинной прогулке по направленному графу — но не слишком длинной, так как циклов нет. Вы начинаете с вершины 0, и всякий раз, когда вы находитесь в вершине, вы случайным образом покидаете её по одному из исходящих рёбер с вероятностью, пропорциональной весу ребра.
Вы продолжаете идти, пока не достигнете вершины, из которой нет исходящих рёбер, после чего засыпаете. Длина вашего пути — это количество рёбер, которые вы проходите. Более того, перед тем как покинуть вершину 0, вы можете выбрать одно ребро из любого места в графе, которое вам не нравится, и игнорировать его во время вашей прогулки (или можете выбрать не игнорировать ни одно из них). Определите наибольшую возможную ожидаемую длину вашего пути.
Входные данные
Входные данные состоят из нескольких тестов. Каждый тест начинается с строки, содержащей два целых числа N, 2 ≤ N ≤ 10000, и M, 1 ≤ M ≤ 100000, количество вершин и рёбер в графе соответственно. Следующие M строк содержат по три целых числа u, v и w (1 ≤ w ≤ 1000), указывающие на то, что существует направленное ребро из вершины u в вершину v (нумерация от 0 до N−1) с весом w. Входные данные заканчиваются строкой с N = M = 0.
Выходные данные
Для каждого теста выведите одну строку, содержащую наибольшую возможную ожидаемую длину вашего пути. Ваш ответ будет считаться правильным, если он будет в пределах 10^{−6} абсолютной или относительной точности.