I. Транспортировка

Со склада (пункт 1) в лагерь (пункт $n$) надо привезти кружки. Пустой грузовик весит 3 тонны, кружка — 100 граммов. На каждой дороге есть ограничение на вес автомобиля и время проезда. Всего на дорогу есть 24 часа, то есть 1440 минут.

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

Первая строка содержит числа $n$ ($1 \le n \le 500$) и $m$ ($0 \le m \le 10^5$).

Далее идут $m$ строк: два пункта, время проезда (не больше 1440) и ограничение на вес в граммах (не больше $10^9$). Дороги двусторонние, соединяют различные пункты, между парой пунктов не более одной дороги.

Одно число — наибольшее количество кружек, или $-1$, если даже пустой грузовик не успевает.