Busy Beaver 正在探索 MIT 的地下校園。校園內有 $N$ 座建築物，編號為 $1, \dots, N$，以及 $M$ 條隧道，編號為 $1, \dots, 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$)。

保證從建築物 $1$ 出發，攜帶有限數量的硬幣即可到達建築物 $N$。

輸出格式

輸出一個整數，代表答案。

子任務

• ($20$ 分) 共有 $N-1$ 條隧道：對於所有 $1 \le i < N$，有一條連接建築物 $i$ 與 $i+1$ 的隧道。
• ($20$ 分) 對於所有 $1 \le i \le M$，$r_i = 0$。
• ($20$ 分) 對於所有 $1 \le i \le M$，$c_i = r_i$。
• ($20$ 分) 對於所有 $1 \le i \le M$，$c_i \ge r_i$。
• ($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$ 枚硬幣作為回報（因此他到達建築物 $2$ 時有 $4-2+1=3$ 枚硬幣），然後使用這 $3$ 枚硬幣通過從建築物 $2$ 到建築物 $3$ 的隧道。

範例說明 2

如果 Busy Beaver 起始時有 $3$ 枚硬幣，他可以先通過從建築物 $1$ 到建築物 $2$ 的隧道，到達時剩下 $1$ 枚硬幣。接著他可以前往建築物 $3$，之後他會有 $2$ 枚硬幣。最後，他可以支付 $2$ 枚硬幣通過隧道到達建築物 $4$，並在到達時獲得 $4$ 枚硬幣。

範例說明 3

Busy Beaver 可以從建築物 $1$ 開始攜帶 $4$ 枚硬幣，通過隧道 $2$ 三次，以 $10$ 枚硬幣進入隧道 $4$，並以 $9$ 枚硬幣到達建築物 $3$。可以證明，若 Busy Beaver 起始時攜帶少於 $4$ 枚硬幣，則無法到達建築物 $3$。