1. 

// Simon Baumgartner, WA

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

public class Main {

/**
* holds all possible connections
*/
private static ArrayList<Connection> CONNECTIONS;

/**
* holds all computers in this network
*/
private static ArrayList<Computer> COMPUTERS;

/**
* global variable to hold the cheapest network computed so far
*/
private static Network CHEAPEST;

/**
* to enumerate networks read from input
*/
private static int NETWORK_COUNT = 1;


public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
// BufferedReader in = new BufferedReader(new FileReader("input.txt"));
int lines = Integer.parseInt(in.readLine());

while(lines != 0){

// parse computers from input
COMPUTERS = new ArrayList<Computer>();
for(int i = 1; i <= lines; i++){
String[] token = in.readLine().split(" ");
COMPUTERS.add(new Computer(Integer.parseInt(token[0]), Integer.parseInt(token[1])));
}

// populate connections
CONNECTIONS = new ArrayList<Connection>();
for(int i = 0; i<COMPUTERS.size(); i++)
for(int j = i+1; j<COMPUTERS.size(); j++)
CONNECTIONS.add(new Connection(COMPUTERS.get(i), COMPUTERS.get(j)));

CHEAPEST = null;

Network network = new Network(NETWORK_COUNT, COMPUTERS.size());
backtrack(network);
System.out.println(CHEAPEST);

lines = Integer.parseInt(in.readLine());
NETWORK_COUNT++;
}
}

/**
* returns only if a solution is found or there are no candidates left.
* updates CHEAPEST if the given network is cheaper.
* calls itself recursively for each new candidate.
* @param network
*/
private static void backtrack(Network network){
if(network.isValid()){
if(CHEAPEST == null || CHEAPEST.totalDistance > network.totalDistance)
CHEAPEST = network;
}
else{
List<Connection> candidates = makeCandidates(network);
for(Connection candidate : candidates){
Network tmp = network.clone();
tmp.addConnection(candidate);
backtrack(tmp);
}
}
}

/**
* returns all possible valid connections that are left in the given network
* @param network
* @return
*/
private static LinkedList<Connection> makeCandidates(Network network) {

LinkedList<Connection> candidates = new LinkedList<Connection>();
for(Connection con : CONNECTIONS){
if(network.allowsConnection(con))
candidates.add(con);
}
return candidates;
}
}


class Computer implements Comparable<Computer>{
private final int x;
private final int y;

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

public String toString(){
return "(" + x + "," + y + ")";
}

public double distanceTo(Computer other){
return Math.sqrt(Math.pow(Math.abs(this.x - other.x), 2) + Math.pow(Math.abs(this.y - other.y), 2)) + 16;
}

public int compareTo(Computer o) {
int a = x*10 + y;
int b = o.x*10 + o.y;
return new Integer(a).compareTo(new Integer(b));
}

@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + x;
result = prime * result + y;
return result;
}

@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Computer other = (Computer) obj;
if (x != other.x)
return false;
if (y != other.y)
return false;
return true;
}


}

class Connection implements Comparable<Connection>{

public Computer first;
public Computer second;

private double distance = 0.0;

public Connection(Computer first, Computer second){
this.first = first;
this.second = second;
}

public double getDistance(){
if(distance == 0.0)
distance = first.distanceTo(second);
return distance;
}

public String toString(){
// return first + " -- " + second;
return "Cable requirement to connect " + first + " to " + second + " is " + String.format("%.2f", getDistance()) + " feet.";
}

public int compareTo(Connection o) {
Connection other = (Connection) o;
return new Double(this.getDistance()).compareTo(new Double(other.getDistance()));
}
}

class Network{
private static final int MAXIMUM_CONNECTIONS_PER_COMPUTER = 2;
private final int validNrOfComputers;
private final int number;

private ArrayList<Connection> connections = new ArrayList<Connection>();

/**
* keeps track of the nr of connections per computer
*/
private HashMap<Computer, Integer> connectionsPerComputer = new HashMap<Computer, Integer>();

public double totalDistance = 0.0;

public Network(int nr, int validNrOfComputers){
this.number = nr;
this.validNrOfComputers = validNrOfComputers;
}

/**
* returns wether at least one new computer will be connected by adding this connection
* and if the network is still valid afterwards
* @param con the connection to be checked
* @return
*/
public boolean allowsConnection(Connection con) {
Integer countFirst = connectionsPerComputer.get(con.first);
Integer countSecond = connectionsPerComputer.get(con.second);

// if both are already in the network
if(countFirst != null && countSecond != null)
return false;

// if one of them already has 2 connections
if((countFirst != null && countFirst >= 2) || (countSecond != null &&countSecond >= 2))
return false;

return true;
}

/**
* checks of the network is valid in its current state.
* @return
*/
public boolean isValid() {
// all computers have to be connected and the number of connection is one smaller than the number of computers
if(connections.size() + 1 == connectionsPerComputer.keySet().size() && connectionsPerComputer.keySet().size() == validNrOfComputers){

int oneCount = 0;
for(Integer count : connectionsPerComputer.values()){
// if one computer has more than 2 connections it's not valid
if(count > MAXIMUM_CONNECTIONS_PER_COMPUTER)
return false;
if(count == 1){
oneCount++;
}
}
// there must only be 2 computers with one connection, the start and the end of the network
return oneCount == 2;
}
else
return false;
}

/**
* adds a connectiont to this network
* @param con
* @return
*/
public boolean addConnection(Connection con){
if(addComp(con.first) && addComp(con.second)){
connections.add(con);
totalDistance += con.getDistance();
return true;
}
else
return false;
}

/**
* helper method for addConnection
* @return false if adding this connection will leave the network invalid, true otherwise
* @param comp
*/
private boolean addComp(Computer comp){
if(connectionsPerComputer.containsKey(comp)){
int count = connectionsPerComputer.get(comp);
if(count + 1 <= MAXIMUM_CONNECTIONS_PER_COMPUTER)
connectionsPerComputer.put(comp, count + 1);
else{
return false;
}
}
else{
connectionsPerComputer.put(comp, 1);
}
return true;
}

public String toString(){
String ret = "*********************************************\n";
ret += "Network #" + number + "\n";
for(Connection con : connections)
ret += con.toString() + "\n";
ret += "Number of feet of cable required is " + String.format("%.2f", totalDistance);
return ret;
}

public Network clone(){
Network net = new Network(this.number, this.validNrOfComputers);
net.connections = (ArrayList<Connection>) this.connections.clone();
net.connectionsPerComputer = (HashMap<Computer, Integer>) this.connectionsPerComputer.clone();
net.totalDistance = this.totalDistance;
return net;
}
}