К очередному Чемпионату Урала было решено подготовить кружки с символикой чемпионата не только для участников, но и для всех желающих.

Имея привычку делать важные дела в самый последний момент, дизайнер закончил работу над макетом за два дня до начала регистрации участников. Ещё день уйдёт у завода-изготовителя на то, чтобы изготовить кружки и нанести на них изображение. На то, чтобы довезти кружки от завода-изготовителя до места проведения соревнования, остаётся всего 24 часа.

Заказ на десять миллионов экземпляров кружек (а именно столько заказали организаторы), конечно же, за один рейс не увезти. Однако, за первый рейс хочется привезти максимальное количество кружек.

Для перевозки был заказан один большегрузный автомобиль. Но есть один нюанс: на некоторых дорогах установлено ограничение на вес автомобиля. Поэтому если автомобиль нагрузить кружками под завязку, то, возможно, не удастся воспользоваться самым коротким маршрутом, а придётся ехать в объезд. Может случиться даже так, что из-за этого грузовик не успеет доехать до места проведения соревнования вовремя, а этого допустить никак нельзя.

Итак, сколько же кружек можно погрузить в автомобиль, чтобы успеть привезти этот ценный груз вовремя, и не нарушая правил дорожного движения?

В первой строке находятся числа N (1 ≤ N ≤ 500) и M — количество узловых пунктов дорожной схемы и количество дорог, соответственно. В следующих M строках находится информация о дорогах. Каждая дорога описывается в отдельной строке следующим образом. Сначала указаны номера узловых пунктов, которые соединяются данной дорогой. Потом время, которое тратится на проезд по этой дороге. И, наконец, максимальный вес автомобиля, которому разрешено ехать по этой дороге. Известно, что все дороги соединяют различные пункты, причем для каждой пары пунктов есть не более одной дороги, непосредственно их соединяющей. Все числа разделены одним или несколькими пробелами.

Узловые пункты нумеруются числами от 1 до N. При этом завод по производству кружек имеет номер 1, а место проведения Чемпионата Урала — номер N. Время проезда по дороге задано в минутах и не превосходит 1440 (24 часа). Ограничение на массу задано в граммах и не превосходит одного миллиарда. Кроме того, известно, что одна кружка весит 100 грамм, а пустой грузовик — 3 тонны.

Выведите одно число — максимальное количество кружек, которое можно привезти за первый рейс, потратив не более 24 часов.