Дано неорієнтований граф з \(N\) вершин. Необхідно опрацювати \(Q\) операцій настпуних типів:
A B C D W - додати неорієнтовані ребра вагою \(W\) з усіх вершин відрізка \([A..B]\) в усі вершини відрізка \([C..D]\)

Після всіх операцій додавання ребер знайдіть найкоротший шлях з вершини \(1\) до вершини \(N\).

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

Перший рядок містить три цілих числа \(N,Q\) (\(1 \le N \le 5*10^4\) , \(1 \le Q \le 10^4\))
Наступні \(Q\) рядків містять опис запитів \(A B C D W\) (\(1 \le A,B,C,D \le N\), \(1 \le W \le 10^3\)).

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

Виведіть найкоротшу відстань від вершини \(1\) до вершини \(N\) (якщо шляху не існує, виведіть -1)

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

5 3
1 2 4 5 42
5 5 4 4 468
1 1 3 3 335

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

42