Фермер Джон недавно купил новую ферму чтобы расширить свою молочную империю. Новая ферма соединена с соседним городом сетью труб, и ФД хочет найти их лучший набор, который можно купить для перекачки молока с фермы в город.

Сеть трубопроводов описывается n точками соединения (конечными точками труб), пронумерованных с 1 до n. Точка соединения 1 является фермой ФД, а точка соединения n является городом. В наличии имеются m двунаправленных труб, каждая из которых соединяет две точки соединения. i - ая труба стоит ci долларов, которую ФД может купить для своего использования, и может поддерживать скорость потока fi литров молока в секунду.

ФД хочет приобрести трубы для одного пути, где конечными точками являются соединения 1 и n. Стоимость пути - это сумма стоимости труб вдоль пути. Скорость потока вдоль пути - это минимум из пропускных способностей труб вдоль пути (поскольку он служит узким местом для потока на пути). ФД хочет максимизировать пропускную способность, разделенную на стоимость пути. Гарантируется, что такой путь от 1 до n существует.

Входные данные

Первая строка содержит числа n (2 ≤ n ≤ 1000) и m (1 ≤ m ≤ 1000). Каждая из следующих m строк описывает трубу в виде четырех целых чисел: a и b (два разных соединения, соединенных трубой), c (стоимость) и е (пропускная способность). Стоимость и пропускная способность являются натуральными числами в диапазоне от 1 до 1000.

Выходные данные

Выведите оптимальный ответ, умноженный на 106, усеченный до целого числа (то есть округленный до ближайшего наименьшего целого числа, если это число само не является целым).

Пример

В примере имеется только один путь от 1 до n. Его пропускная способность равна min(3, 4) = 3, а стоимость равна 2 + 5 = 7.