Busy Beaver eksploruje podziemny kampus MIT. Istnieje $N$ budynków oznaczonych numerami $1,\dots,N$ oraz $M$ tuneli oznaczonych numerami $1,\dots,M$, łączących pewne pary budynków. $i$-ty tunel łączy budynek $a_i$ z budynkiem $b_i$. Aby do niego wejść, należy najpierw zapłacić $c_i$ monet. Jednak po przejściu przez tunel i docenieniu jego walorów artystycznych, otrzymuje się nagrodę w wysokości $r_i$ monet.

Busy Beaver mieszka w budynku $1$ i musi dotrzeć na wykład w budynku $N$. Jaka jest minimalna liczba monet, które musi ze sobą zabrać, aby móc dotrzeć do budynku $N$?

Pamiętaj o następujących zasadach:

• Tunele można przemierzać w dowolnym kierunku, dowolną liczbę razy. Każde przejście wiąże się z uiszczeniem opłaty i otrzymaniem nagrody.
• Busy Beaver może wykorzystać otrzymane nagrody do opłacenia przyszłych opłat za wejście do tuneli.
• Pomiędzy dwoma budynkami może istnieć więcej niż jeden tunel.
• Liczba posiadanych monet nigdy nie może być ujemna.

Wejście

Pierwsza linia zawiera dwie liczby całkowite oddzielone spacją, $N$ oraz $M$ ($2\le N \le 10^5$, $1\le M \le 2\cdot 10^5$).

Kolejne $M$ linii opisuje tunele. $i$-ta z nich składa się z czterech liczb całkowitych oddzielonych spacją: $a_i$, $b_i$, $c_i$ oraz $r_i$ ($1 \le a_i,b_i \le N$, $a_i \ne b_i$, $0 \le c_i,r_i \le 10^9$).

Gwarantuje się, że budynek $N$ jest osiągalny z budynku $1$ przy posiadaniu skończonej liczby monet.

Wyjście

Wypisz w jednej linii odpowiedź.

Podzadania

• ($20$ punktów) Istnieje $N-1$ tuneli: jeden tunel łączący budynek $i$ z budynkiem $i+1$ dla wszystkich $1 \le i < N$.
• ($20$ punktów) $r_i = 0$ dla wszystkich $1 \le i \le M$.
• ($20$ punktów) $c_i = r_i$ dla wszystkich $1 \le i \le M$.
• ($20$ punktów) $c_i \ge r_i$ dla wszystkich $1 \le i \le M$.
• ($20$ punktów) Brak dodatkowych ograniczeń.

Przykład

Przykład 1

3 3
1 2 2 1
2 3 3 0
1 3 5 0

Wyjście 1

4

Przykład 2

4 3
1 2 3 1
2 3 1 2
3 4 2 4

Wyjście 2

3

Przykład 3

3 4
1 2 4 3
1 2 4 6
2 1 5 4
2 3 10 9

Wyjście 3

4

Uwagi

Wyjaśnienie przykładu 1

Jeśli Busy Beaver zacznie z $4$ monetami, może najpierw przejść przez tunel z budynku $1$ do budynku $2$, płacąc $2$ monety i otrzymując $1$ monetę w nagrodę (po przybyciu do budynku $2$ ma $4-2+1=3$ monety), a następnie przejść przez tunel z budynku $2$ do budynku $3$, używając swoich $3$ monet.

Wyjaśnienie przykładu 2

Jeśli Busy Beaver zacznie z $3$ monetami, może najpierw przejść przez tunel z budynku $1$ do budynku $2$, mając $1$ monetę po przybyciu. Następnie może przejść do budynku $3$, po czym będzie miał $2$ monety. Na koniec może dotrzeć do budynku $4$, płacąc $2$ monety i otrzymując $4$ monety po przybyciu.

Wyjaśnienie przykładu 3

Busy Beaver może zacząć w budynku $1$ z $4$ monetami, przejść przez tunel $2$ trzy razy, wejść do tunelu $4$ z $10$ monetami i dotrzeć do budynku $3$ z $9$ monetami. Można wykazać, że Busy Beaver nie jest w stanie dotrzeć do budynku $3$, zaczynając z mniej niż $4$ monetami.