// Arup Guha
// Started 6/2014, finished on 10/14/2014
// Solution to 2012 World Finals Problem: Minimum Cost Flow

import java.util.*;

public class g {

	final public static double IMPOSSIBLE = 1000000000;

	public static int n;
	public static int e;
	public static junction[] pts;
	public static ArrayList[] eList;
	public static int minZ;
	public static double[][] allDist;

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int loop = 1;

		// Go through each case.
		while (stdin.hasNext()) {

			n = stdin.nextInt();
			e = stdin.nextInt();

			// Read in junctions.
			minZ = -10000;
			pts = new junction[n];
			allDist = new double[n][n];

			for (int i=0; i<n; i++) {
				int[] tmp = new int[3];
				for (int j=0; j<3; j++)
					tmp[j] = stdin.nextInt();
				int holes = stdin.nextInt();
				pts[i] = new junction(tmp, holes, i+1);

				// Easier to calculate this now.
				if ((i == 0 || i == n-1) && tmp[2] > minZ) minZ = tmp[2];
			}

			Arrays.sort(pts);

			// Create look up table for new vertex assignments.
			int[] lookUp = new int[n+1];
			for (int i=0; i<n; i++)
				lookUp[pts[i].ID] = i;

			// Precomp to save time.
			for (int i=0; i<n; i++)
				for (int j=0; j<n; j++)
					allDist[i][j] = pts[i].dist(pts[j]);

			// Read in edges - with new labels.
			eList = new ArrayList[n];
			for (int i=0; i<n; i++)
				eList[i] = new ArrayList<Integer>();
			for (int i=0; i<e; i++) {
				int v1 = lookUp[stdin.nextInt()];
				int v2 = lookUp[stdin.nextInt()];
				eList[v1].add(v2);
				eList[v2].add(v1);
			}

			// Solve and output.
			double res = solve(lookUp[1], lookUp[n]);
			if (Math.abs(res-IMPOSSIBLE) < 1e-9)
				System.out.println("Case "+loop+": impossible");
			else
				System.out.printf("Case %d: %.4f\n", loop, res);

			// Get next case.
			loop++;
		}
	}

	// Finds the minimum distance from vertex startI to vertex endI.
	public static double solve(int startI, int endI) {

		// Set up first boundary for search.
		int end = 0;
		while (end < n && pts[end].coord[2] <= minZ) end++;

		// Get initial result.
		double res = IMPOSSIBLE;

		// Go until the end.
		while (true) {

			// Solve this subgraph and update if necessary.
			double cur = eval(startI, endI, end);
			if (cur < res) res = cur;

			if (end == n) break;

			// Go to end of next unique z value.
			int nextZ = pts[end].coord[2];
			int start = end;
			while (end < n && pts[end].coord[2] == nextZ) end++;
		}

		// Final result.
		return res;
	}

	// Evaluate the graph for this disjoint set arrangement.
	public static double eval(int startI, int endI, int end) {

		// solve for connected components in this subgraph.
		int[] components = getComponents(end);
		ArrayList[] compList = getCompList(components, end);

		// Count holes in each component.
		int[] compHoles = new int[compList.length];
		for (int i=0; i<compList.length; i++)
			for (int j=0; j<compList[i].size(); j++)
				compHoles[i] += pts[((ArrayList<Integer>)compList[i]).get(j)].numHoles;

		// Set up BFS.
		PriorityQueue<state> pq = new PriorityQueue<state>();
		state[][] visited = new state[end][2];
		for (int i=0; i<end; i++) Arrays.fill(visited[i], null);

		// Run a modified BFS to get the result.
		pq.offer(new state(0, startI, pts[startI].numHoles>0, compHoles[components[startI]]));
		while (pq.size() > 0) {

			// Get next state.
			state next = pq.poll();
			visited[next.vertex][next.canLeave ? 1:0] = next;

			// We got there!
			if (next.vertex == endI) return next.total();

			// Store this component.
			int myComp = components[next.vertex];

			// Enqueue free neighbors.
			for (int i=0; i<compList[myComp].size(); i++) {

				int item = ((ArrayList<Integer>)compList[myComp]).get(i);
				int myLeave = pts[item].numHoles>0 ? 1:0;
				state potential = new state(next.weight, item, myLeave==1, next.holes);

				// Add to queue if we haven't gotten there yet or this is faster. Remove old node in queue.
				if (visited[item][myLeave] == null || visited[item][myLeave].total() > potential.total()) {
					pq.remove(visited[item][myLeave]);
					visited[item][myLeave] = potential;
					pq.offer(potential);
				}
			}

			// Enqueue items in different components.
			if (next.canLeave) {

				// Go to new components - only if hole exists in vertex.
				for (int i=0; i<end; i++) {
					if (components[i] != myComp && pts[i].numHoles > 0) {

						state potential = new state(next.weight+allDist[next.vertex][i]-1, i, pts[i].numHoles > 1, next.holes+compHoles[components[i]]);
						int index = pts[i].numHoles > 0 ? 1 : 0;

						// Add to queue if we haven't gotten there yet or this is faster. Remove old node in queue.
						if (visited[i][index] == null || visited[i][index].total() > potential.total()) {
							pq.remove(visited[i][index]);
							visited[i][index] = potential;
							pq.offer(potential);
						}
					}
				}
			}
		} // end pq.size() > 0

		// Never made it.
		return IMPOSSIBLE;
	}

	// Returns a list of each component of the subgraph nodes[0..end-1].
	public static int[] getComponents(int end) {

		int[] visited = new int[end];
		Arrays.fill(visited, -1);
		int compNum = 0;

		// Usual connected components code.
		for (int i=0; i<end; i++) {
			if (visited[i] == -1) {
				dfs(i, compNum, visited, end);
				compNum++;
			}
		}
		return visited;
	}

	// Inverts the component list craeted by getComponents, for quick look-up.
	public static ArrayList[] getCompList(int[] components, int end) {

		int numC = -1;
		for (int i=0; i<end; i++)
			if (components[i]+1 > numC)
				numC = components[i]+1;

		ArrayList[] list = new ArrayList[numC];
		for (int i=0; i<numC; i++)
			list[i] = new ArrayList<Integer>();

		for (int i=0; i<end; i++)
			if (components[i] >= 0)
				list[components[i]].add(i);

		return list;
	}

	public static void dfs(int index, int compNum, int[] visited, int end) {

		visited[index] = compNum;
		for (int i=0; i<eList[index].size(); i++) {
			int next = ((ArrayList<Integer>)eList[index]).get(i);
			if (next < end && visited[next] == -1)
				dfs(next, compNum, visited, end);
		}
	}

}

// Stores a state for our breadth first search - info to calculate cost to this state.
class state implements Comparable<state> {

	public double weight;
	public int vertex;
	public boolean canLeave;
	public int holes;

	public state(double w, int v, boolean holeLeft, int numHoles) {
		weight = w;
		vertex = v;
		canLeave = holeLeft;
		holes = numHoles;
	}

	public double total() {
		return weight + holes/2.0;
	}

	public int compareTo(state other) {
		if (this.total() < other.total()-1e-10) return -1;
		else if (this.total() > other.total()+1e-10) return 1;
		return 0;
	}
}

// Stores a node that we can sort by Z-coordinate.
class junction implements Comparable<junction> {

	public int[] coord;
	public int numHoles;
	public int ID;

	public junction(int[] pt, int k, int index) {
		coord = pt;
		numHoles = k;
		ID = index;
	}

	public int compareTo(junction other) {
		return this.coord[2] - other.coord[2];
	}

	public double dist(junction other) {
		double sumsq = 0;
		for (int i=0; i<3; i++)
			sumsq += ((coord[i]-other.coord[i])*(coord[i]-other.coord[i]));
		return Math.sqrt(sumsq);
	}
}