Фермер Джон нещодавно купив нову ферму, щоб розширити свою імперію виробництва молока. Нова ферма з'єднана з найближчим містом мережею труб, і ФД хоче відібрати найкращу підмножину цих труб для покупки з метою передачі молока з ферми до міста.

Мережа труб описується \(N\) точками з'єднання (кінцевими точками труб), послідовно пронумерованих \(1 \ldots N\) (\(2 \leq N \leq 1000\)). Точка з'єднання 1 являє собою нову ферму Джона, а точка з'єднання \(N\) представляє місто. Є \(M\) двонаправлених труб (\(1 \leq M \leq 1000\)), кожна з яких з'єднує дві точки з'єднання. \(i\)-а труба коштує \(c_i\) доларів і може підтримувати передачу молока зі швидкістю \(f_i\) літрів у секунду.

ФД хоче купити один шлях (найвигідніший) із труб, кінцевими точками якого будуть точки \(1\) та \(N\). Вартість шляху дорівнює сумі вартості труб вздовж цього шляху. Швидкість передачі молока по дорозі дорівнює мінімальній швидкості передачі труб (Мінімальна ланка буде вузьким місцем шляху). ФД хоче максимізувати швидкість передачі, поділену на вартість шляху. Гарантується існування шляху з \(1\) у \(N\).

ОЦІНЮВАННЯ:

• Тести 2-5 задовольняють \(N,M\le 100.\)

Формат вхідних даних

Перший рядок введення містить \(N\) і \(M\). Кожен із наступних \(M\) рядків описує трубу чотирма цілими числами \(a\) і \(b\) (дві різні точки з'єднання, з'єднаними цією трубою), \(c\) (її вартість), \(f\) (її продуктивність - швидкість передачі молока). \(c\) і \(f\) обидва цілі позитивні числа в інтервалі \(1 \ldots 1000\).

Формат вихідних даних

Виведіть оптимальне значення, помножене на \(10^6\), обрізане до цілого (тобто округлене донизу до найближчого цілого числа, якщо це число не ціле).

Приклад вхідних даних

3 2
2 1 2 4
2 3 5 3

Приклад вихідних даних

428571

У цьому прикладі є один шлях з \(1\) в \(N.\), його потік (продуктивність) дорівнює \( \min (3,4) = 3 \) а його вартість \( 2 +5 = 7 \).