Компания "Яндекс" решила подарить всем школьникам и преподавателям ЛКШ оригинальные кружки. К сожалению, количество необходимых кружек оказалось столь велико, что изготовитель доставил кружки в офис Яндекса в самый последний момент. На то, чтобы довезти кружки из Москвы до "Берендеевых полян" осталось всего \textbf{24} часа. Заказ на \textbf{10^7} экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек. Для перевозки был заказан один большегрузный автомобиль. Но есть один ньюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому, если автомобиль нагрузить кружками под завязку, то, возможно, не удастся восплользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случится даже так, что из-за этого грузовик не успеет доехать до лагеря вовремя, а этого допустить никак нельзя. Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя и не нарушить правила дорожного движения? \InputFile В первой строке находятся числа \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{500}) и \textbf{m} - количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих \textbf{m} строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой, потом время, которое тратится на проезд по этой дороге, и, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причём для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами. Узловые пункты нумеруются числами от \textbf{1} до \textbf{n}. При этом офис "Яндекса" имеет номер \textbf{1}, а "Берендеевы поляны" - номер \textbf{n}. Время проезда по дороге задано в минутах и не превосходит \textbf{1440} (\textbf{24} часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит \textbf{100} грамм, а пустой грузовик - \textbf{3} тонны. \OutputFile Выведите одно число - максимальное количество кружек, которое можно привезти за первый рейс, потратив не более \textbf{24} часов.