Taxi!

• Taxi driver: "Where to, sir?"
• Passenger: "Kemanggisan, Binus Campus, please."
• Taxi driver: "Okay, and which way should I take?"
• Passenger: "Just take the fastest one."

This is the kind of conversation we often have when taking a taxi. Many people assume that the fastest route is also the cheapest one, but that is not always true. Because of factors such as toll fees, or a longer detour that avoids traffic jams, a faster route can end up costing more, and vice versa.

In this problem we model exactly this situation. A city has $n$ intersections and $m$ bidirectional roads connecting pairs of intersections. Traversing each road costs a fixed amount of time and a fixed fare (taxi money). Write a program that finds the minimum time to reach your destination without spending more than the money you have.

The input consists of several test cases; process each case in order until the end of input.

The first line of each case contains two integers $n$ ($1 \le n \le 100$, the number of intersections) and $m$ (the number of roads). Intersections are numbered from $0$ to $n-1$.

Each of the next $m$ lines contains four integers $u$, $v$, $t$, and $c$ ($1 \le t, c \le 100$), meaning there is a bidirectional road between intersections $u$ and $v$ that takes $t$ minute(s) and costs $c$ Rupiah to traverse.

The last line of each case contains three integers $s$, $d$, and $r$ ($1 \le r \le 100$), meaning you want to travel from the starting point $s$ to the destination $d$ using only $r$ Rupiah.

For each case, output on a single line the minimum time to reach the destination while the total cost does not exceed your money.

It is guaranteed that the destination is always reachable within the given budget.