Випадкова прогулянка у DAG#3378
Ви досліджуєте орієнтований граф із вершинами та ребрами. Граф не містить циклів. Ви починаєте у вершині . У кожній вершині ви випадковим чином вибираєте одне з її вихідних ребер, причому ймовірність вибору кожного ребра пропорційна його вазі.
Ви продовжуєте дослідження, доки не потрапите у вершину, з якої немає вихідних ребер. Довжина вашого шляху дорівнює кількості ребер, які ви пройдете. Крім того, перед початком вашого проходження з вершини , ви можете видалити з графа одне ребро (або ж не видаляти жодного). Знайдіть найбільшу можливу очікувану довжину вашого шляху з урахуванням найкращого вибору ребра, яке можна ігнорувати (або не видаляти жодного).
Вхід складається з кількох тестів. Кожен тест починається рядком, який містить два цілі числа , 2 \leq N \leq 10000, і , 1 \leq M \leq 100000 — кількість вершин та ребер у графі. Наступні рядків містять по три цілі числа , , (1 \leq w \leq 1000), що означає наявність орієнтованого ребра з вершини у вершину (вершини нумеруються від до N-1) з вагою . Вхід закінчується рядком з N = M = 0.
Для кожного тесту виведіть у окремому рядку максимальну можливу очікувану довжину вашого проходження. Ваша відповідь буде вважатися правильною, якщо абсолютна або відносна похибка не перевищує 10^{-6}.
Приклад 1