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$ монет.