Busy Beaver исследует подземный кампус MIT. Всего есть $N$ зданий, пронумерованных от $1$ до $N$, и $M$ туннелей, пронумерованных от $1$ до $M$, соединяющих некоторые пары зданий. $i$-й туннель соединяет здания $a_i$ и $b_i$. Чтобы войти в него, вы должны сначала заплатить $c_i$ монет. Однако после прохода через туннель и осмотра его достопримечательностей вы получаете вознаграждение в размере $r_i$ монет.

Busy Beaver живет в здании $1$ и собирается посетить лекцию в здании $N$. Какое минимальное количество монет ему нужно взять с собой, чтобы добраться до здания $N$?

Учтите следующее:

• Туннели можно проходить в любом направлении любое количество раз. Каждый раз при проходе взимается плата и выплачивается вознаграждение.
• Busy Beaver может использовать полученные монеты для оплаты будущих проходов.
• Между двумя зданиями может быть более одного туннеля.
• Количество монет никогда не может быть отрицательным.

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

Первая строка содержит два целых числа, разделенных пробелом: $N$ и $M$ ($2\le N \le 10^5$, $1\le M \le 2\cdot 10^5$).

Следующие $M$ строк описывают туннели. $i$-я из них состоит из четырех целых чисел, разделенных пробелом: $a_i$, $b_i$, $c_i$ и $r_i$ ($1 \le a_i,b_i \le N$, $a_i \ne b_i$, $0 \le c_i,r_i \le 10^9$).

Гарантируется, что здание $N$ достижимо из здания $1$ при наличии конечного количества монет.

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

Выведите одно число — ответ на задачу.

Подзадачи

• ($20$ баллов) Всего $N-1$ туннель: один туннель соединяет здание $i$ со зданием $i+1$ для всех $1 \le i < N$.
• ($20$ баллов) $r_i = 0$ для всех $1 \le i \le M$.
• ($20$ баллов) $c_i = r_i$ для всех $1 \le i \le M$.
• ($20$ баллов) $c_i \ge r_i$ для всех $1 \le i \le M$.
• ($20$ баллов) Дополнительных ограничений нет.

Примеры

Пример 1

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

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

4

Пример 2

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

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

3

Пример 3

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

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

4

Примечание

Пояснение к примеру 1

Если Busy Beaver начинает с $4$ монетами, он может сначала пройти через туннель из здания $1$ в здание $2$, заплатив $2$ монеты и получив $1$ монету в качестве вознаграждения (в итоге у него $4-2+1=3$ монеты по прибытии в здание $2$), а затем пройти через туннель из здания $2$ в здание $3$, используя свои $3$ монеты.

Пояснение к примеру 2

Если Busy Beaver начинает с $3$ монетами, он может сначала пройти через туннель из здания $1$ в здание $2$, имея $1$ монету по прибытии. Затем он может отправиться в здание $3$, после чего у него будет $2$ монеты. Наконец, он может добраться до здания $4$, заплатив $2$ монеты и получив $4$ монеты по прибытии.

Пояснение к примеру 3

Busy Beaver может начать в здании $1$ с $4$ монетами, пройти через туннель $2$ три раза, войти в туннель $4$ с $10$ монетами и прибыть в здание $3$ с $9$ монетами. Можно показать, что Busy Beaver не может добраться до здания $3$, имея менее $4$ монет.