#include <stdio.h>
#define maxval 2100000000
int t,i,j,k,n,nant,p,nr,l;
int c[2][13100][20],lvl[2][20][2];
void redec()
{
     int i,j,k;
     k=(1<<n)-1;     
     for (i=0; i<=k; i++)
          for (j=1; j<=n; j++)
              c[l][i][j]=maxval;
}
int sqr(int x)
{
    return x*x;    
} 
int dist()
{
    return sqr(lvl[1-l][j][0]-lvl[l][i][0])+sqr(lvl[1-l][j][1]-lvl[l][i][1]);
}
int main()
{
    freopen("bibel.in","r",stdin);
    freopen("bibel.out","w",stdout);
    
    nr=0;l=0;
    while (p!=2)
    {
	   nr++;
	   nant=n;
	   n=0;
	   l=1-l;
	   scanf("%d",&p);
	   if (p==2) break;
       while (p==0)
       {
           n++;
		   scanf("%d %d",&lvl[l][n][0],&lvl[l][n][1]);
           scanf("%d",&p);
       }

       //initializare matrice
       if (nr==1)    
       {
          redec();          
		  for (i=1; i<=n; i++)
			c[l][1<<(i-1)][i]=sqr(lvl[l][i][0])+sqr(lvl[l][i][1]);
       }
       else
       {
          redec();
          for (i=1; i<=n; i++)
              for (j=1; j<=nant; j++) 
              {
				  if (c[l][1<<(i-1)][i]>c[1-l][(1<<nant)-1][j]+dist())
					 c[l][1<<(i-1)][i]=c[1-l][(1<<nant)-1][j]+dist();
              }
       }

       //fac dinamica optima pentru nivelul i
       t=(1<<n)-1;
	   for (i=0; i<=t; i++)
           for (j=1; j<=n; j++)
		   {
			   if (i&(1<<(j-1)))
				   for (k=1; k<=n; k++)
				   if (j!=k && (i&(1<<(k-1)))==0)
				   {
					   if (c[l][i+(1<<(k-1))][k]>c[l][i][j]+sqr(lvl[l][k][0]-lvl[l][j][0])+sqr(lvl[l][k][1]-lvl[l][j][1]))
					   c[l][i+(1<<(k-1))][k]=c[l][i][j]+
					   sqr(lvl[l][k][0]-lvl[l][j][0])+
					   sqr(lvl[l][k][1]-lvl[l][j][1]);
				   }
		   }
       int min=maxval;
       for (i=1; i<=n; i++)
		   if (c[l][t][i]<min) min=c[l][t][i];
       
       printf("%d\n",min);
    }
    
    
    return 0;    
}