ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1886. Перелёт 2

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Денис спит и видит сон, в котором он прошёл через сито отборочных раундов, получил загранпаспорт и американскую визу и отправился в заокеанский город Вас-Легас на соревнования по укладке кирпичей.
И вот он оказался в аэропорту. К сожалению, организаторы согласились оплатить ему перелёт только при условии, что он будет пользоваться услугами авиакомпании Oceanic Airlines. Её рейсы имеют дурную славу — хоть они и вылетают всегда по расписанию, но из-за метеорологических, экономических и геополитических причин прибытие очень часто задерживается на значительное время. Впрочем, Денис знает полное расписание рейсов и вероятность задержки каждого рейса. Кроме того, он не будет покупать билеты заранее. Сначала он купит билет только на первый рейс. После прибытия в первый аэропорт назначения он выберет и купит билет на второй рейс — и так далее, пока не доберётся до Вас-Легаса.
Денис будет выбирать каждый билет так, чтобы в итоге гарантированно попасть в Вас-Легас и при этом минимизировать матожидание времени прибытия туда. Помогите Денису оценить, сколько времени он потратит на дорогу.

Исходные данные

В первой строке записаны целые числа n и m — количество аэропортов и рейсов Oceanic Airlines, соответственно (2 ≤ n ≤ 100 000; 1 ≤ m ≤ 100 000). Денис прибыл в аэропорт номер 1, аэропорт Вас-Легаса имеет номер n. Далее идёт описание m рейсов. Каждый из них описывается шестью целыми числами a, b, t, f, p, d — номерами аэропортов вылета и назначения, временем вылета, длительностью полёта, вероятностью задержки рейса (в процентах) и величиной задержки, соответственно. (1 ≤ t, d, f ≤ 109; 1 ≤ a, bn; ab; 1 ≤ p ≤ 99). Все времена указаны в минутах. Время отправления рейсов отсчитывается от момента, когда Денис прибыл в самый первый аэропорт. Известно, что Денис умеет делать пересадку мгновенно.

Результат

Выведите ожидаемое время в минутах, которое Денис потратит на путешествие в Вас-Легас. Ответ нужно вывести с абсолютной или относительной погрешностью не более 10−6. Если Денис не может гарантировать, что он доберётся до Вас-Легаса, выведите «Fail».

Примеры

исходные данныерезультат
4 5
1 4 10 10 90 20
1 2 5 5 50 5
2 4 15 10 50 5
2 3 1 14 10 1
3 4 15 1 50 1
27.500
2 1
2 1 20 19 50 1
Fail
Автор задачи: Денис Дублённых
Источник задачи: NEERC 2011, Четвертьфинал Восточного подрегиона