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