#include <stdio.h>
#define maxval 2147000000
#define put2 131100
int t,i,j,k,n,nant,p,nr,l;
int c[put2][20],lvl[2][20][2];
int val[put2];
void redec()
{
     int i,j,k;
     k=(1<<n)-1;     
     for (i=0; i<=k; ++i)
          for (j=1; j<=n; ++j)
              c[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[1<<(i-1)][i]=sqr(lvl[l][i][0])+sqr(lvl[l][i][1]);
       }
       else
       {
                    
          for (i=1; i<=nant; ++i)
              val[i]=c[(1<<nant)-1][i];
          redec();
          for (i=1; i<=n; ++i)
              for (j=1; j<=nant; ++j) 
              {
				  if (c[1<<(i-1)][i]>val[j]+dist())
					 c[1<<(i-1)][i]=val[j]+dist();
              }
	   }

       //fac dinamica 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[i+(1<<(k-1))][k]>c[i][j]+sqr(lvl[l][k][0]-lvl[l][j][0])+sqr(lvl[l][k][1]-lvl[l][j][1]))
					   c[i+(1<<(k-1))][k]=c[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[t][i]<min) min=c[t][i];  */
       
       printf("%d\n",min);
    }
    
    
    return 0;    
}