Don't be late

Junha is an ordinary university student. He botched course registration this semester, so his timetable is a mess and he has to move between many buildings between classes.

Every building has a name, but writing out full names each time wasted ink. So when there are $N$ buildings to move between, he calls them Building 1 through Building $N$.

With that many buildings he was late often. Junha is in Building 1 right now, and if he misses this class held in Building $N$ he gets an F.

To avoid being late he often took a taxi, and he wrote down in his notebook the travel time and the taxi fare between buildings. He had only a few pages left, so he never wrote down a road twice. There is only one road between any two buildings, so the same road was never recorded with a different time or a different fare. The time and the fare are the same in both directions.

He is on academic probation, so he will not risk taking a new road that is not in the notebook.

Below is a case with 5 buildings.

His class in Building 1 has just ended and he has to reach Building 5 within 3 hours. He opened the notebook in a hurry, but he cannot tell which way to go.

Junha has only 4,000 won, and he has to live on it for the rest of the month, so he wants to spend as little as possible.

This will keep happening, so he gave up on this class and asked you for a general program.

Given the travel time and the taxi fare between buildings and the money he has now, write a program that prints the minimum amount he can spend to arrive within $T$ minutes.

The first line contains the number of buildings $N$ ($2 \le N \le 100$).

The second line contains the time left until the class $T$ ($1 \le T \le 10000$, in minutes) and the money he has now $M$ ($0 \le M \le 10000$), in that order.

The third line contains the number of roads between buildings written in the notebook, $L$ ($1 \le L \le 10000$).

Each of the next $L$ lines contains the numbers of the two buildings at the ends of a road, the travel time of that road in minutes, and the taxi fare. The travel time and the taxi fare are natural numbers not greater than 10,000. The two building numbers on a line are different.

If Junha can go from building 1 to building $N$ within $T$ minutes while spending at most $M$, print the minimum amount spent.

If he cannot, print -1.

In the figure above, going from Building 1 through Building 3 and Building 4 to Building 5 arrives within 3 hours for 3,500 won. Fortunately the class was cancelled that day.