410029: GYM103920 G Magnetic Backpack

Everyone loves collecting rocks! That is, everyone except you.

You are stuck in a big cave, with your trusty magnetic backpack. The cave consists of $$$n$$$ caverns connected by $$$m$$$ tunnels. You start at cavern $$$1$$$ and the exit as at cavern $$$n$$$. Each tunnel has $$$a$$$ magnetic rocks that will automatically stick to your backpack once you enter the tunnel. However, each tunnel also has its own magnetic field, and will take away $$$b$$$ rocks once you leave (or all of your rocks, if you have less than $$$b$$$ rocks).

You hate collecting rocks, so you must figure out how to leave with the least number of rocks, if you even can escape this cave.

The first line contains two integers, $$$n$$$ ($$$1 \leq n \leq 300$$$) and $$$m$$$ ($$$1 \leq m \leq n(n-1)$$$).

Then, $$$m$$$ lines follow, each containing four integers: $$$x$$$, $$$y$$$ ($$$1 \leq x, y \leq n$$$) and $$$a$$$, $$$b$$$ ($$$0 \leq a, b \leq 10$$$). This denotes a one-way tunnel from cavern $$$x$$$ to cavern $$$y$$$, where you gain $$$a$$$ rocks upon entering and lose $$$b$$$ rocks upon leaving.

Output a single integer, the minimum number of rocks you can leave the cave with, or -1 if it is not possible to escape the cave.

4 4
1 2 10 0
2 4 2 1
4 3 0 5
3 2 3 3

1

In the example, a path that achieves this is 1 -> 2 -> 4 -> 3 -> 2 -> 4 -> 3 -> 2 -> 4 -> 3 -> 2 -> 4. In order, the number of stones you have is: 0, 10, 11, 6, 6, 7, 2, 2, 3, 0, 0, 1.