Brave Princess Revisited

A tomboyish, brave princess of a poor country is to be married off to another country for political reasons. A villain who wants her dead has placed assassins along the road to her new home.

To deliver the princess safely to the other country, you had already chosen a safe route, but at her stubborn earnest wish to travel a road she has never taken before, you take a different road. So you decide to choose the road the princess will travel again, looking at the map.

Every road is a highway connecting two post stations. For convenience, the starting point and the destination are also post stations. The new road, however, has problems with public order. There is a high chance that bandits or assassins who want the princess dead will attack.

To travel such a dangerous road, it is desirable to hire guards. Guards can be hired at a post station, and can be made to protect the princess road by road. While a guard is protecting her, she is not attacked by bandits or assassins, but it costs 1 gold per unit of distance. Therefore, to hire a guard, your money on hand must be no less than the distance to the next post station.

Now, under the given budget L, you want to minimize the number of bandits and assassins that attack before the princess safely reaches the destination. Your job is to find that minimized number. She is not attacked while at a post station.

The input consists of multiple datasets. Each dataset has the following format.

N M L
A1 B1 D1 E1
A2 B2 D2 E2
...
AN BN DN EN

The first line gives three non-negative integers N (2 ≤ N ≤ 100), M, and L (0 ≤ L ≤ 100). These integers represent the number of post stations, the number of roads, and the budget for hiring guards. Post stations are numbered from 1 to N, with the starting point numbered 1 and the destination numbered N.

The following M lines give road information, one road per line. A road is given by four integers A**i, B**i (1 ≤ A**i < B**i ≤ N), D**i (1 ≤ D**i ≤ 100), and E**i (0 ≤ E**i ≤ 10000). They represent the numbers of the starting and ending post stations of the road, the distance of the road, and the number of bandits and assassins encountered on it.

Roads can be traveled in both directions, and for any pair of post stations there is at most one road. It is guaranteed that the destination is reachable from the starting point.

The end of the input is indicated by a line containing three zeros separated by spaces.

For each dataset, output the minimum number of bandits and assassins encountered, one per line. Do not include extra spaces or line breaks in the output.