#include<stdio.h>
#include<string.h>
struct point
{
	int x,y;
};
int n,n1=1;
int c[1<<17][18];
int di[20][20];
int d[20];
point v[20],v1[20];

inline int dist(point p1, point p2)
{
	return (p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y);
}

void set()
{
	int i,j;
	for(i=0;i<(1<<17);i++)
		for(j=0;j<=17;j++)
			c[i][j]=(1<<30)-1;
}

void distp()
{
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			di[i][j]=dist(v[i],v[j]);
}

void init()
{
	int i,j;
	for(i=0;i<n1;i++)
		for(j=0;j<n;j++)
			if(c[1<<j][j]>d[i]+dist(v1[i],v[j]))
				c[1<<j][j]=d[i]+dist(v1[i],v[j]);
}

void rez()
{
	int i,j,k;
	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) && (c[j+(1<<k)][k]>c[j][i]+di[i][k]))
						c[j+(1<<k)][k]=c[j][i]+di[i][k];
}

int main()
{
	freopen("bibel.in","r",stdin);
	freopen("bibel.out","w",stdout);
	int ch,i;
	scanf("%d",&ch);
	while(ch!=2)
	{
		while(ch==0)
		{
			n++;
			scanf("%d%d%d",&v[n-1].x,&v[n-1].y,&ch);
		}
		set();
		distp();
		init();
		rez();
		ch=1<<30;
		for(i=0;i<n;i++)
		{
			d[i]=c[(1<<n)-1][i];
			if(ch>d[i])
				ch=d[i];
		}
		printf("%d\n",ch);
		n1=n;
		n=0;
		memcpy(v1,v,sizeof(v));
		scanf("%d",&ch);
	}
	return 0;
}