Денис спит и видит сон, в котором он прошёл через сито отборочных раундов, получил загранпаспорт и американскую визу и отправился в заокеанский город Вас-Легас на соревнования по укладке кирпичей.

И вот он оказался в аэропорту. К сожалению, организаторы согласились оплатить ему перелёт только при условии, что он будет пользоваться услугами авиакомпании 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 ≤ 10⁹; 1 ≤ a, b ≤ n; a ≠ b; 1 ≤ p ≤ 99). Все времена указаны в минутах. Время отправления рейсов отсчитывается от момента, когда Денис прибыл в самый первый аэропорт. Известно, что Денис умеет делать пересадку мгновенно.

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