#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;
}
inline int dist()
{
    return (lvl[1-l][j][0]-lvl[l][i][0])*(lvl[1-l][j][0]-lvl[l][i][0])+(lvl[1-l][j][1]-lvl[l][i][1])*(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]=lvl[l][i][0]*lvl[l][i][0]+lvl[l][i][1]*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]+(lvl[l][k][0]-lvl[l][j][0])*(lvl[l][k][0]-lvl[l][j][0])+(lvl[l][k][1]-lvl[l][j][1])*(lvl[l][k][1]-lvl[l][j][1]))
					      c[i+(1<<(k-1))][k]=c[i][j]+(lvl[l][k][0]-lvl[l][j][0])*(lvl[l][k][0]-lvl[l][j][0])+(lvl[l][k][1]-lvl[l][j][1])*(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;    
}