Компанія "Яндекс" вирішила подарувати усім школярам та викладачам ЛКШ оригінальні кружки. На жаль, кількість необхідних кружок виявилась настільки великою, що виробник доставив кружки у офіс Яндекса у самий останній момент. На те, щоб довезти кружки з Москвы до "Берендеєвих полян" залишилось усього \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} годин.