П'яний хід
Після вечора з надмірним вживанням алкоголю ви опиняєтеся на прогулянці по орієнтованому графу. На щастя, ця прогулянка не буде занадто довгою, адже в графі немає циклів. Ви починаєте з вершини 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} абсолютної або відносної точності.