Исследовательский ровер перемещается между контрольными точками на поверхности планеты. Маршруты между точками образуют взвешенный ориентированный граф из n вершин и m рёбер.

Для каждого маршрута известны две стоимости прохождения:

• w1 — если ровер едет в обычном режиме;
• w2 — если ровер едет в турбо-режиме.

Ровер начинает путь в вершине 1 в обычном режиме. В любой вершине он может один раз за всё путешествие включить турбо-режим. После этого ровер уже не может вернуться обратно и продолжает движение только в турбо-режиме до конца пути. Также допускается вовсе не включать турбо-режим.

Требуется определить минимальную суммарную стоимость пути из вершины 1 в вершину n.

Если добраться до вершины n невозможно, выведите -1.

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

Первая строка содержит два целых числа n и m — количество вершин и рёбер.

Каждая из следующих m строк содержит четыре целых числа u, v, w1, w2 — ребро из вершины u в вершину v, стоимость прохождения этого ребра в обычном режиме и стоимость прохождения в турбо-режиме соответственно.

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

Выведите одно целое число — минимальную возможную стоимость пути из вершины 1 в вершину n, либо -1, если такой путь не существует.

Ограничения

• 2 <= n <= 200000
• 0 <= m <= 300000
• 1 <= u, v <= n
• 0 <= w1, w2 <= 1000000

Примеры

Пример 1

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

2 1
1 2 5 3

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

3

Пример 2

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

4 5
1 2 10 100
2 4 10 100
1 3 100 1
3 4 100 1
2 3 1 1

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

2