#include<stdio.h>
#include<string.h>
struct qq {int x,y;};
int n,n1=1,l[131072][18],X[20][20],d[20],i,j,k;
qq v[20],v1[20];
inline int Xst(qq f, qq g)
{return (g.x-f.x)*(g.x-f.x)+(g.y-f.y)*(g.y-f.y);}
int main()
{freopen("bibel.in","r",stdin);
freopen("bibel.out","w",stdout);
scanf("%d",&k);
while(k!=2)
   {while(k==0)
	  {n++;
	  scanf("%d%d%d",&v[n-1].x,&v[n-1].y,&k);}
  for(i=0;i<(131072);i++)
    for(j=0;j<=17;j++)
	  l[i][j]=(1073741824)-1;
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      X[i][j]=Xst(v[i],v[j]);
  for(i=0;i<n1;i++)
    for(j=0;j<n;j++)
      if(l[1<<j][j]>d[i]+Xst(v1[i],v[j]))
	   l[1<<j][j]=d[i]+Xst(v1[i],v[j]);
  for(j=0;j<(1<<n);j++)
    for(i=0;i<n;i++)
	  if(j&(1<<i))
	   for(k=0;k<n;k++)
	     if(((j&(1<<k))==0) && (l[j+(1<<k)][k]>l[j][i]+X[i][k]))
	      l[j+(1<<k)][k]=l[j][i]+X[i][k];
   k=1073741824;
   for(i=0;i<n;i++)
     {d[i]=l[(1<<n)-1][i];
	 if(k>d[i])
	  k=d[i];}
   printf("%d\n",k);
   n1=n;
   n=0;
   memcpy(v1,v,sizeof(v));
   scanf("%d",&k);}
return 0;}