Vampire Tunnels

You are a vampire, and you want to travel from point 0 to point $N-1$. You may walk above ground, exposed to sunlight, or avoid the sun by travelling underground through secret tunnels. Both the tunnels and the above-ground paths are bidirectional.

You move at a constant speed of $1$ unit of distance per second, so travelling along a path of length $d$ takes $d$ seconds. You may be exposed to sunlight for at most $S$ seconds in total. Minimize the total travel time from point 0 to point $N-1$ while respecting this limit.

The first line contains the integer $S$ ($0 \le S \le 3600$), the maximum number of seconds you may be exposed to the sun.

The second line contains two integers $N$ ($2 \le N \le 1600$) and $E$ ($1 \le E \le 10000$), separated by a single space: the number of points and the number of connections. The points are numbered from 0 to $N-1$.

Each of the next $E$ lines contains four integers $s$, $t$, $d$, $u$ describing one connection:

• $s$, $t$ ($0 \le s, t \le N-1$, $s \ne t$): the two endpoints of the connection
• $d$ ($1 \le d \le 10000$): the distance (travel time) between $s$ and $t$
• $u$: $1$ if the connection is above ground (exposed to sun), or $0$ if it is a tunnel (underground, no sun exposure)

Output a single integer: the minimum time needed to travel from point 0 to point $N-1$ while spending at most $S$ seconds exposed to the sun. If no path satisfies this constraint, output $-1$.