#include<fstream.h>
#include<stdio.h>
#define inf 999999
#define min(a,b) (a < b ? a : b)

struct poz 
	   {
	   	   int l,c;
		   } x[100],t[100];


int dist(poz a, poz b)
    {
    int r=(a.l-b.l)*(a.l-b.l)+(a.c-b.c)*(a.c-b.c);
    return r;   
    }
int mat[10000][10000],i,j,k,numarture,p,pune[1000],n,r,y[1000];

int main()
{
int a=0;numarture=1;
t[1].l=0;
t[1].c=0;
freopen("bibel.in","r",stdin);
freopen("bibel.out","w",stdout);
while (a!=2)
    {
    scanf("%d",&a);
    if (a==2)
        return 0;   
    n=0;
    while (a!=1)
        {
        n++;
        scanf("%d%d",&x[n].l,&x[n].c);
        scanf("%d",&a);
        }
    for(i=0;i<=20;i++)
    				  pune[i]=1<<i;
	for(i=0;i<=p;i++)
	for(j=1;j<=n;j++)
			mat[i][j]=inf;
			for(i=1;i<=numarture;i++)
			mat[pune[n-j]][j]=min(dist(t[i],x[j])+y[i],mat[pune[n-j]][j]);
			for(i=0;i<p;j++)
				for(j=1;j<=n;j++)
			if((pune[n-j])&i)
							 for(k=1;k<=n;k++)
			if((pune[n-k]&i)==0)
			
					mat[i|(pune[n-k])][k]=min(mat[i|pune[n-k]][k],mat[i][j]+dist(x[j],x[k]));		
	p=1<<n;
	r=inf;n=numarture;
	for(i=1;i<=n;i++)
 					 {
					 y[i]=mat[p-1][i];
					 t[i].l=x[i].l;
					 t[i].c=x[i].c;
					 if(mat[p-1][i]<r)
					 		r=mat[p-1][i];
					}
	printf("%d\n",r);
}
return 0;
}