Busy Beaver is exploring the underground MIT campus. There are $N$ buildings labelled $1,\dots,N$ and $M$ tunnels labelled $1,\dots,M$ connecting certain pairs of buildings. The $i^\text{th}$ tunnel connects building $a_i$ and $b_i$. In order to enter it, you must first pay $c_i$ coins. However, after walking through the tunnel and appreciating its art, you are rewarded with $r_i$ coins.

Busy Beaver lives in building $1$ and will attend his lecture in building $N$. What's the minimum number of coins he needs to bring with him to be able to reach building $N$?

Keep in mind the following:

• Tunnels can be traversed in any direction, any number of times. Each time you go through, the fee is incurred and the reward is collected.
• Busy Beaver can use the coins he is rewarded with to pay future entrance fees.
• There may be more than one tunnel connecting two buildings.
• You can never have a negative number of coins.

Input

The first line contains two space separated integers, $N$ and $M$ ($2\le N \le 10^5$, $1\le M \le 2\cdot 10^5$).

The next $M$ lines describe the tunnels. The $i^\text{th}$ of them consists of four space separated integers, $a_i$, $b_i$, $c_i$, and $r_i$ ($1 \le a_i,b_i \le N$, $a_i \ne b_i$, $0 \le c_i,r_i \le 10^9$).

It is guaranteed that building $N$ is reachable from building $1$ starting with a finite number of coins.

Output

Output one line with the answer.

Scoring

• ($20$ points) There are $N-1$ tunnels: one tunnel connecting building $i$ to building $i+1$ for all $1 \le i < N$.
• ($20$ points) $r_i = 0$ for all $1 \le i \le M$.
• ($20$ points) $c_i = r_i$ for all $1 \le i \le M$.
• ($20$ points) $c_i \ge r_i$ for all $1 \le i \le M$.
• ($20$ points) No additional constraints.

Examples

Input 1

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

Output 1

4

Input 2

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

Output 2

3

Input 3

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

Output 3

4

Note

Sample Explanation 1

If Busy Beaver starts with $4$ coins, he can first go through the tunnel from building $1$ to building $2$, paying $2$ coins and getting $1$ coin in return (so he has $4-2+1=3$ coins when he arrives at building $2$), then go through the tunnel from building $2$ to building $3$ using his $3$ coins.

Sample Explanation 2

If Busy Beaver starts with $3$ coins, he can first go through the tunnel from building $1$ to building $2$, with $1$ coin when he arrives. Then he can go to building $3$, after which he has $2$ coins. Finally, he can reach building $4$ by paying $2$ coins and getting $4$ coins when he arrives.

Sample Explanation 3

Busy Beaver can start in building $1$ with $4$ coins, traverse through tunnel $2$ $3$ times, enter tunnel $4$ with $10$ coins, and arrive at building $3$ with $9$ coins. It can be shown that Busy Beaver cannot reach building $3$ starting with fewer than $4$ coins.