Old Factory Plumbing

You have been hired to build a system that carries water between two points in an old factory, reusing parts of the building's old plumbing. The old plumbing consists of pipes and junctions. A junction is a point where pipes were once joined. Some of the old pipes were damaged and removed, which left open holes in the junctions they used to connect. If water ever reaches an open hole, it pours out and floods the building — an outcome you must avoid.

You can fix this by installing new pipes between open holes and by installing plugs to close other open holes. A new pipe joins two open holes that lie in two different junctions; once it is installed, those two holes are closed and water can flow through the new pipe. The cost of a new pipe equals the Euclidean distance between the centers of the two junctions it connects. The cost of one plug is $0.5$. You do not care about open holes in junctions that water never reaches.

Two junctions are special: the source (junction $1$), where water is pumped in, and the destination (junction $N$), where water is needed. After all plugs and new pipes are installed, water is pumped in at the source with a pressure that raises it to a height of your choosing. The pressure is constant and you may choose it freely, but it must be at least large enough to raise water to the heights of both the source and the destination. Your task is to find the cheapest way to bring water from the source to the destination without flooding the building.

Water obeys the following rules. If the pressure is enough to fill a junction, that junction stays filled. From a filled junction, water always flows through pipes that go horizontally or downward, and it flows through an upward pipe only up to the height set by the pressure. Concretely, if the water level you choose is $H$, then water fills exactly those junctions whose height is at most $H$ and that are connected to the source through a pipe path passing only through junctions of height at most $H$. If water reaches an open hole in any filled junction, the building floods.

Existing pipes and new pipes never interfere with one another, nor with any junction other than the ones they connect (even if the straight segment between two junctions passes through a third junction, the pipe does not touch it).

The input contains several test cases and ends at end of file.

The first line of each test case contains two integers $N$ and $M$, where $N$ ($2 \le N \le 400$) is the number of junctions (numbered $1$ through $N$) and $M$ ($0 \le M \le 50000$) is the number of existing usable pipes.

Each of the next $N$ lines contains four integers $x_i$, $y_i$, $z_i$, and $k_i$ with $-10000 \le x_i, y_i, z_i \le 10000$ and $0 \le k_i \le 400$. Line $i$ describes junction $i$: $(x_i, y_i, z_i)$ is its position, where the $z$-axis is vertical, and $k_i$ is the number of open holes in it.

Each of the next $M$ lines contains two integers $a_j$ and $b_j$ with $1 \le a_j < b_j \le N$, meaning that pipe $j$ connects junctions $a_j$ and $b_j$. At most one pipe connects any pair of junctions, and no two junctions share the same coordinates. The source is junction $1$ and the destination is junction $N$.

For each test case, output one line in the form Case x: v, where x is the test case number starting from $1$. If it is possible to connect the source to the destination without flooding the building, v is the minimum total cost, printed to exactly four decimal places. Otherwise v is the word impossible.