Difficult Routes

In preparation for the coming Olympics, you have been asked to propose bicycle training routes for your national cycling team. The training committee wants to identify routes between pairs of locations at several sites around the country. Each route must have a desired level of difficulty based on the steepness of its hills.

You are given a road map with elevation data superimposed on it. Each intersection, where two or more roads meet, is identified by its $x$-, $y$-, and $z$-coordinates. Each road starts and ends at an intersection, is straight, and does not contain bridges over or tunnels under other roads. A road may be cycled in either direction, and its difficulty depends on the direction of travel.

The difficulty level $d$ of cycling a road is $0$ if the road is level or is travelled in the downhill direction. The difficulty of a non-level road travelled in the uphill direction is $\lfloor 100 \cdot \text{rise} / \text{run} \rfloor$, where rise is the absolute change in elevation and run is the distance between its two endpoints in their horizontal projection onto the plane at elevation zero. (Cycling a descending road always has difficulty $0$.)

The length of a road is the straight-line (3D Euclidean) distance between its two endpoints. A route is a sequence of roads in which each road continues from the intersection where the previous road ended; the length of a route is the sum of the lengths of its roads. A route has difficulty $d$ if the maximum difficulty among all of its roads equals $d$. For a chosen pair of locations, the committee wants the route with the required difficulty that has the shortest possible total length.

Reminder: the floor function $\lfloor X \rfloor$ means $X$ truncated to an integer.

The figure below shows a road map with three intersections, corresponding to the sample input.

The edge labels on the darker shaded surface give the uphill difficulty levels. The lighter shaded surface is the horizontal projection onto the plane at elevation zero.

The input consists of several road maps. Each map begins with two non-negative integers $N$ and $M$ on a line by themselves, separated by a space, giving the number of intersections and the number of roads, respectively ($0 < N, M \le 10000$). A line containing $N = 0$ and $M = 0$ marks the end of the input.

Each of the next $N$ lines contains three integers, separated by single spaces, giving the $x$-, $y$-, and $z$-coordinates of an intersection. Each coordinate is between $0$ and $10000$, inclusive. Intersections are numbered starting from $1$ in the order they appear. Each of the following $M$ lines contains two integers, the two endpoint intersections of a road (a road may be cycled in either direction).

Finally, a line with three integers $s$, $t$, and $d$ gives the desired start intersection $s$, finish intersection $t$, and required difficulty level $d$ for the training route ($0 \le d \le 10$). A valid training route must contain at least one road of difficulty exactly $d$ and no road of difficulty greater than $d$. If the route is a closed circuit, then $s$ and $t$ are the same intersection.

For each road map, print a single line containing either:

1. the shortest length of a valid training route, rounded to exactly three decimal places (always printing all three decimal digits); or
2. the single word None if no feasible route exists.

Reminder — how to round a positive number of the form R.xxxy to three decimal places:

• If the fourth decimal digit y is less than 5, the result is R.xxx.
• Otherwise, the result is R.xxx + 0.001.

For example, 10.3463 is printed as 10.346, and 10.3695 is printed as 10.370.