Shortest Path Delivery

You are given a set of warehouses and roads connecting them. Each road is defined by the coordinates of two warehouses and a maximum capacity. The Euclidean distance between two warehouses connected by a road is calculated by \(\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}\). You are also given a required quantity of goods to deliver. You must determine the shortest delivery path from a source warehouse to a destination warehouse using only roads that have a capacity greater than or equal to the required quantity.

If there is no such path, output -1.

inputFormat

The input is read from stdin and consists of multiple test cases. For each test case:

• The first line contains two integers M and N, where M is the number of warehouses and N is the number of roads.
• The next N lines each contain five integers: x1 y1 x2 y2 capacity, representing the coordinates of the two warehouses connected by the road and the road's capacity.
• The following line contains five integers: sx sy dx dy quantity, where (sx, sy) is the source warehouse, (dx, dy) is the destination warehouse, and quantity is the amount to be delivered.
• The input ends with a line containing "0 0" for M and N.

outputFormat

For each test case, output a single line to stdout containing the length of the shortest path rounded to 10 decimal places, or -1 if it is impossible to deliver the goods.

3 3
0 0 10 0 100
10 0 10 10 50
10 10 0 10 50
0 0 10 10 50
0 0

20.0000000000