Empire

Jiyong tore up a calculus textbook and built a raft of thickness $K$, thick enough to carry one person. He now plans to leave port A and sail to the uninhabited island B to found his empire.

The sea holds $N$ islands and $M$ sea routes. Nothing outside a sea route is passable, so Jiyong sails from island to island. Sea route $i$ takes time $t_i$ to cross and shaves $h_i$ centimeters off the raft.

Once the total $h_i$ of the crossed routes reaches $K$, the raft falls to a thickness of 0cm or less and Jiyong, who cannot swim, does not survive. The voyage is safe only while the total $h_i$ of the crossed routes stays below $K$.

Find the safe voyage from A to B that takes the least time and print that time. He may pass through the same island or the same sea route more than once, and every crossing adds its time and its damage again.

The first line has three integers $K$, $N$, $M$. ($1 \le K \le 200$, $2 \le N \le 2000$, $1 \le M \le 10000$)

Each of the next $M$ lines describes one sea route as $u$, $v$, $t_i$, $h_i$. ($1 \le u, v \le N$, $u \ne v$, $1 \le t_i \le 100000$, $0 \le h_i \le 200$) A two-way sea route connects island $u$ and island $v$, crossing it takes time $t_i$, and it shaves $h_i$ off the raft. Several sea routes may connect the same pair of islands.

The last line has the start $A$ and the destination $B$. ($1 \le A, B \le N$, $A \ne B$)

Print the minimum time of a safe voyage from A to B, or -1 if Jiyong cannot sail there safely.