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$ 往返 $3$ 次，携带 $10$ 枚硬币进入隧道 $4$，并以 $9$ 枚硬币到达建筑 $3$。可以证明，Busy Beaver 若携带少于 $4$ 枚硬币则无法到达建筑 $3$。