2012WF G

#include <iomanip>
#include <cmath>
#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
const ld INF = 1e12;
ll N, x[400], y[400], z[400], k[400];
vector<int> adjl[400];
int par[400]; ld cost[400][400];
ld d[400];
struct dcomp {
  bool operator()(const int& a, const int& b) const {
   return d[a] < d[b] || (d[a] == d[b] && a < b);
  }
};

int Find(int i) { return par[i]==i ? i : (par[i] = Find(par[i])); }
void Union(int i, int j) { int pi = Find(i), pj = Find(j);
  if (pi == pj) return;
  k[pj] += k[pi];
  for (int l=0; l < N; l++) {
    if (Find(l) == pi)
      cost[pj][l] = cost[l][pj] = 0;
    else if (par[l] == l)
      cost[pj][l] = cost[l][pj] = min(cost[pj][l], cost[pi][l]);
  }
  par[pi] = pj;
}

int main() {
    ios::sync_with_stdio(0);
    int M, zz=1;
    while(cin >> N >> M) {
        map<int, vector<int> > heights;
        for (int i=0; i < N; i++) {
          cin >> x[i] >> y[i] >> z[i] >> k[i];
          par[i] = i;
          heights[z[i]].push_back(i);
        }
        for (int i=0; i < N; i++) adjl[i].clear();
        for (int i=0; i < M; i++) {
            int a, b; cin >> a >> b; a--; b--;
            adjl[a].push_back(b);
            adjl[b].push_back(a);
        }
        for (int i=0; i < N; i++) for (int j=0; j < N; j++) {
          if (k[i] == 0 || k[j] == 0) cost[i][j] = 2*INF;
          else cost[i][j] = sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j])+0.L);
        }

        ld best = INF;
        for (map<int, vector<int> >::iterator it = heights.begin(); it != heights.end(); it++) {
          int h = it->first; vector<int> &todo = it->second;
          for (int i=0; i < todo.size(); i++)
            for (int j=0; j < adjl[todo[i]].size(); j++)
              if (z[adjl[todo[i]][j]] <= h)
                Union(todo[i], adjl[todo[i]][j]);

          if (h < z[0] || h < z[N-1]) continue;
          for (int i=0; i < N; i++) d[i] = INF;
          int st = Find(0);
          d[st] = k[st]*0.5;
          set<int, dcomp> q; q.insert(st);
          while(q.size()) {
            int next = *q.begin(); q.erase(q.begin());
            for (int i=0; i < N; i++) if (par[i] == i && i != next && z[i] <= h) {
              if (next != st && k[next] == 1) continue;
              ld tcost = d[next] + cost[next][i] + k[i]*0.5 - 1;
              if (tcost < d[i]) {
                q.erase(i);
                d[i] = tcost;
                q.insert(i);
              }
            }
          }
          best = min(best, d[Find(N-1)]);
        }
        cout << "Case " << zz++ << ": ";
        if (best >= INF) cout << "impossible" << endl;
        else cout << fixed << setprecision(4) << best << endl;
    }
    return 0;
}