#include<fstream.h>
#include<stdio.h>
#define inf 999999
#define min(a,b) (a < b ? a : b)

struct poz 
	   {
	   	   int l,c;
		   } x[100],t[100];


long dist(poz a, poz b)
    {
    long r=(a.l-b.l)*(a.l-b.l)+(a.c-b.c)*(a.c-b.c);
    return r;   
    }
long mat[10000][10000],i,j,k,numarture,p,pune[1000],n,r,y[1000];

int main()
{
long a=0;
numarture=1;
t[1].l=0;
t[1].c=0;
y[1]=0;

for(i=0;i<=20;i++)
    				  pune[i]=1<<i;
ifstream in("bibel.in");
ofstream out("bibel.out");
while (a!=2)
    {
    in>>a;
    if (a==2)
        return 0;   
    n=0;
    while (a!=1)
        {
        n++;
        in>>x[n].l>>x[n].c;
        in>>a;
		}
    p=1<<n;
	for(i=0;i<=p;i++)
	for(j=1;j<=n;j++)
			mat[i][j]=inf;
	for(i=1;i<=numarture;i++)
		for(j=1;j<=n;j++)	
			mat[pune[n-j]][j]=min(dist(t[i],x[j])+y[i],mat[pune[n-j]][j]);
	for(i=0;i<p;i++)
		for(j=1;j<=n;j++)
			if((pune[n-j])&i)
			 for(k=1;k<=n;k++)
			if((pune[n-k]&i)==0)
					mat[i|(pune[n-k])][k]=min(mat[i|pune[n-k]][k],mat[i][j]+dist(x[j],x[k]));		
	r=inf;numarture=n;
	for(i=1;i<=n;i++)
 					 {
					 y[i]=mat[p-1][i];
					 t[i].l=x[i].l;
					 t[i].c=x[i].c;
					 if(mat[p-1][i]<r)
					 		r=mat[p-1][i];
					}
	out<<r;
	}
return 0;
}