10911

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>

using namespace std;
struct HOUSE{
	double x,y;
};
string str[20];
HOUSE house[20];
double dp[(1<<16)-1];
double d[20][20];
int finalstate;
int n;

double _min(double a,double b)
{
	return a<b?a:b;
}
double DP(int state)
{
	if(state==finalstate)
	return 0;
	if(dp[state]!=-1)
		return dp[state];
	int rest_state = finalstate-state;
	double val=(1<<20);
	for(int i=0;i<2*n;i++)
	{
		if(rest_state&(1<<i))
		{
			for(int j=i+1;j<2*n;j++)
			{
				if(rest_state&(1<<j))
				{
					val = _min(val,d[i][j]+DP(state|(1<<i)|(1<<j) ));
				}
			}
		}
	}
	return dp[state]=val;
}
int main()
{
	int kase=1;
	while(scanf("%d",&n),n)
	{
		for(int i=0;i<(1<<2*n);i++)
			dp[i]=-1;
		finalstate=(1<<2*n)-1;
		for(int i=0;i<20;i++)
			for(int j=0;j<20;j++)
				d[i][j]=0;
		for(int i=0;i<2*n;i++)
		{
			cin>>str[i];
			scanf("%lf%lf",&house[i].x,&house[i].y);
		}
		for(int i=0;i<2*n-1;i++)
		{
			for(int j=i+1;j<2*n;j++)
			{
				d[i][j] = sqrt( (house[i].x-house[j].x)*(house[i].x-house[j].x) + (house[i].y-house[j].y)*(house[i].y-house[j].y) );
				d[j][i] = d[i][j];
			}
		}
		printf("Case %d: %.2lf\n",kase++,DP(0));
	}
	return 0;
}