D. Collecting Coins
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 \lt 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
3 3
1 2 2 1
2 3 3 0
1 3 5 0
Output
4
Input
4 3
1 2 3 1
2 3 1 2
3 4 2 4
Output
3
Input
3 4
1 2 4 3
1 2 4 6
2 1 5 4
2 3 10 9
Output
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.