#include <stdio.h>
#define maxval 2147000000
#define put2 131100

int t,i,j,k,n,nant,p,nr,l,min;
int c[20][put2],lvl[2][20][2];
int val[put2];
int dist[20][20];

void calc_dist()
{
     int i,j;
     for (i=1; i<=n; i++)
         for (j=1; j<=n; j++)
             dist[i][j]=(lvl[l][i][0]-lvl[l][j][0])*(lvl[l][i][0]-lvl[l][j][0])+
                        (lvl[l][i][1]-lvl[l][j][1])*(lvl[l][i][1]-lvl[l][j][1]);
}


void redec()
{
     int i,j,k;

     k=(1<<n)-1;
     for (i=0; i<=k; ++i)
          for (j=1; j<=n; ++j)
              c[j][i]=maxval;
}

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);
       }

       calc_dist();
       
       //initializare matrice
       if (nr==1)    
       {
          redec();
		  for (i=1; i<=n; ++i)
			c[i][1<<(i-1)]=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[i][(1<<nant)-1];

          redec();

          for (i=1; i<=n; ++i)
              for (j=1; j<=nant; ++j) 
				  if (c[i][1<<(i-1)]>val[j]+(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])) 
                     c[i][1<<(i-1)]=val[j]+(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]);
	   }

       //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[k][i+(1<<(k-1))]>c[j][i]+dist[k][j])
					      c[k][i+(1<<(k-1))]=c[j][i]+dist[k][j];
                   }

       min=maxval;
       for (i=1; i<=n; ++i)
		   if (c[i][t]<min) min=c[i][t];  
       
       printf("%d\n",min);
    }
    
    
    return 0;    
}