uva-216

#include<bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define MAX 100005
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);

typedef long long ll;
vector<pair<int,int> >v;
double graph[20][20], TSP;
 int n;
 vector<int> path;

 void path_print(){
  //cerr<<"Enter---\n";
  //for(int i = 0; i < path.size(); i++)cout << path[i] << " ";
    //cout << endl;
  for(int i = 0; i < path.size()-1; i++){
    int x = path[i];
    int y = path[i+1];
    cout <<"Cable requirement to connect ("<<v[x].first<<","<<v[x].second<<") to ("<<v[y].first<<","<<v[y].second<<") is "<<fixed<<setprecision(2)<<graph[x][y]<<" feet.\n";
    cerr << v[x].first << " "<<v[x].second<<endl;
  }
 }

double tsp(int s, double mn)
{
    vector<int>vertex;
    for(int i = 0; i < n; i++){
        if(i != s)
            vertex.push_back(i);
    }

    double min_path = 99999999.0;
    do{
        double current_pathweight = 0.0;
        int k = s;
        for(int i = 0; i < vertex.size(); i++){
            current_pathweight += graph[k][vertex[i]];
            k = vertex[i];
        }
        //current_pathweight += graph[k][s];

        //min_path = min(min_path, current_pathweight);
        if(min_path > current_pathweight && mn > current_pathweight){
          min_path = current_pathweight;
          path.clear();
          path.push_back(s);
          for(int i = 0; i < vertex.size(); i++)path.push_back(vertex[i]);
        }
    }while(next_permutation(vertex.begin(), vertex.end()));
    return min_path;
}

void print()
{
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      cout << setw(3)<<graph[i][j] << " ";
    }
    cout << endl;
  }
}


int main()
{
    //FASTIO
   /* 
   //double start_time = clock();
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
  #endif
    //*/
    int cnt = 0;
    while(cin >> n && n){
      TSP = 0.0;
      for(int i = 0; i < n;i++){
        int x,y;
        cin >> x >> y;
        v.push_back({x,y});
      }
      for(int i = 0; i < n; i++){
        int x1 = v[i].first;
        int y1 = v[i].second;
        for(int j = i+1; j < n; j++){
          int x2 = v[j].first;
          int y2 = v[j].second;
          double D = sqrt(((x1-x2)*(x1-x2)) + ((y1-y2)*(y1-y2))) + 16.0;
          graph[i][j] = D;
          graph[j][i] = D;
         // cerr << x1 << " "<<y1 << " "<<x2 << " "<<y2<<endl;
        }
        //cerr<<"\n";
      }
      //print();
      double mn = 999999.0;
      for(int i = 0; i < n; i++){
         TSP = tsp(i, mn);
         mn = min(TSP, mn);
      }

      cout << "**********************************************************\n";
      cout << "Network #"<<++cnt<<"\n";
      path_print();
      cout <<"Number of feet of cable required is "<<fixed<<setprecision(2)<< mn<<".\n";
      path.clear();
      v.clear();
    }

        //double end_time = clock();
  //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
   
    return 0;
}