import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/**
 * ACM Training 2009
 * ACM Problem #216 - Getting in Line
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=48&problem=152&mosmsg=Submission+received+with+ID+7356798
 *
 * @author Felix Dietrich
 * @version 1.0, 08/31/2009
 *
 * Methode: Backtracking
 * Status : Accepted
 * Runtime: 0.560
 */

public class Main
{
    public static class Computer
    {

        public int y;
        public int x;

        public Computer(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

    }

    public static void main(String... str) throws NumberFormatException, IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //br = new BufferedReader(new FileReader("testfile.txt"));
        
        Map<Integer,List<List<Integer>>> permutations = new HashMap<Integer, List<List<Integer>>>();
        
        for(int i=2; i<=8; i++)
        {
            solutions =  new ArrayList<List<Integer>>();
            track(new ArrayList<Integer>(), 0, i);
            permutations.put(i, solutions);
            
            //System.out.println(i + "! = " + solutions.size());
        }
        
        String input;
        StringTokenizer st;
        List<Computer> compList = new ArrayList<Computer>();
        Map<Integer, List<Integer>> sums = new HashMap<Integer, List<Integer>>();
        
        while((input=br.readLine()) != null)
        {
            int computers = Integer.parseInt(input);
            
            if(computers == 0)
                return;
            
            // read in the computer data
            compList.clear();
            sums.clear();
            for(int c=0; c<computers; c++)
            {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                
                compList.add(new Computer(x,y));
            }
            
            // get the precalculated solutions for this amount of computers
            solutions = permutations.get(computers);
            
            // calculate the sums of all solutions
            for(List<Integer> sol: solutions)
            {
                sums.put(getLen(sol, compList), sol);
            }
            
            int min = Collections.min(sums.keySet());
            printSolution(compList, sums.get(min), min);
        }
    }

    private static int testCase = 1;
    /**
     * Prints the given solution
     * @param list
     * @param min
     */
    private static void printSolution(List<Computer> compList, List<Integer> computerPermutation, int min)
    {
        System.out.println("**********************************************************");
        System.out.println("Network #" + testCase);
        
        int lastI = computerPermutation.get(0);
        Computer c1;
        Computer c2;
        for(int i=1; i<computerPermutation.size(); i++)
        {
            c1 = compList.get(lastI);
            lastI = computerPermutation.get(i);
            c2 = compList.get(lastI);
            System.out.println(String.format("Cable requirement to connect (%d,%d) to (%d,%d) is %.02f feet.", c1.x,c1.y,c2.x,c2.y,getDist(c1,c2)+16));
        }
        
        System.out.println(String.format("Number of feet of cable required is %.02f.",(double)min/100.));
        
        testCase++;
    }

    /**
     * Returns the cable length of the given network solution.
     * @param sol
     * @param compList
     * @return cable length
     */
    private static int getLen(List<Integer> sol, List<Computer> compList)
    {
        double sum = 0;
        int lastIndex = sol.get(0);
        Computer c1;
        Computer c2;
        for(int solNumber=1; solNumber<sol.size(); solNumber++)
        {
            c1 = compList.get(lastIndex);
            lastIndex = sol.get(solNumber);
            c2 = compList.get(lastIndex);
                
            sum += getDist(c1, c2) + 16;
        }
        return (int)Math.round(sum*100.);
    }

    /**
     * Returns the distance between two computers.
     * @param computer1
     * @param computer2
     * @return distance
     */
    private static double getDist(Computer computer1, Computer computer2)
    {
        int dx = computer1.x-computer2.x;
        int dy = computer1.y-computer2.y;
        return Math.sqrt(dx*dx + dy*dy);
    }
    
    ///////////////////////////////////////////////////////////////////
    //// Backtracking part.

    private static List<List<Integer>> solutions;
    private static void track(List<Integer> mySolution, int row, int max)
    {
        if(row >= max)
        {
            solutions.add(mySolution);
            return;
        }
            
        for(int col=0; col<max; col++)
        {
            if(possibleSolution(mySolution, row, col))
            {
                List<Integer> s = new ArrayList<Integer>(mySolution);
                s.add(col);
                track(s, row + 1, max);
            }
        }
    }
    
    // possible solution function for simple permutation
    private static boolean possibleSolution(List<Integer> mySolution, int row, int col)
    {
        if(mySolution.contains(col))
            return false;
        return true;
    }
}