#include <cstdio>

const int Nmax = 17;
const int MAX  = (1<<31) - 1;

#define fin  "bibel.in"
#define fout "bibel.out"

#define DxBG
#define FL

int dp[Nmax][1<<Nmax];
int N1,N2,x1[Nmax],y1[Nmax],x2[Nmax],y2[Nmax];

int sol[Nmax],d[Nmax][Nmax];
int ord[1<<(Nmax+1)];

inline int dist(int xa,int ya,int xb,int yb)
{
	return (xa - xb) * (xa - xb) + (ya - yb) * (ya - yb);
}

inline int min(int a,int b)
{
	if ( a < b ) 
		return a;
	else
		return b;
}

int main()
{
	int i,j,k,dumi=0;
	int ret;
	
//	printf("%d\n",sizeof(dp)/1024);

	freopen(fin,"r",stdin);
#ifdef FL
	freopen(fout,"w",stdout);
#endif

	N1 = 1 ;

	for ( i = 0 ; i <= Nmax ; ++i )
		ord[ 1<<i ] = i;

	for (;;)
	{
		scanf("%d",&dumi);
		
		if ( dumi == 2 )
			break;

		N2 = 0 ;

		while ( dumi == 0 )
		{
			scanf("%d%d",&x2[N2],&y2[N2]);
			++N2;
			scanf("%d",&dumi);
		}

		for ( i = 0 ; i < N2 ; ++i )
		for ( j = 0 ; j < (1<<N2); ++j)
			dp[i][j] = MAX;
		
		for ( i = 0 ; i < N2 ; ++i )
		for ( j = 0 ; j < N2 ; ++j )
			d[i][j] = dist(x2[i],y2[i],x2[j],y2[j]);

		for ( i = 0 ; i < N2 ; ++i )
		{
			dp[i][1<<i]=MAX;
			for ( j = 0 ; j < N1 ; ++j )
				dp[i][1<<i]=min(dp[i][1<<i],sol[j] + dist(x2[i],y2[i],x1[j],y1[j]) );
		}

		for ( k = 0 ; k < ( 1 << N2 ) ; ++k)
		for ( i = 0 ; i < N2 ; ++i )
			if ( ( k & ( 1 << i ) ) == 0 )
			for ( j = k ; j > 0 ; j ^= j & ( ~ ( j - 1 ) ) )
			{
				dp[i][k | ( 1 << i )] = min( dp[i][k | ( 1 << i )] , dp[ ord[ j & ( ~ ( j - 1 ) ) ] ][k] + d[i][ ord[ j & ( ~ ( j - 1 ) ) ] ] );
			}
#ifdef DBG	
		for ( i = 0 ; i < N2 ; ++i)
		{
			for ( j = 0 ; j < ( 1 << N2 ) ; ++j)
				if ( dp[i][j] < MAX )
					printf("%d ",dp[i][j]);
				else
					printf("x ");
			printf("\n");
		}
#endif
		ret = MAX;

		for ( i = 0 ; i < N2 ; ++i )
		{
			x1[i] = x2[i];
			y1[i] = y2[i];
			sol[i] = dp[i][(1<<N2)-1];
			ret = min(ret,sol[i]);
		}

		N1 = N2;

		printf("%d\n",ret);
	}

	return 0;
}