#include<stdio.h>
#include<string.h>
struct point
{
	int x,y;
};
int n,n1=1;
int c[1<<18][20];
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<<18);i++)
		for(j=0;j<20;j++)
			c[i][j]=99;
}

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

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

void rez()
{
	int i,j,k;
	for(j=0;j<(1<<n);j++)
		for(i=1;i<=n;i++)
			if(j&(1<<(i-1)))
				for(k=1;k<=n;k++)
					if(((j&(1<<(k-1)))==0) && (c[j+(1<<(k-1))][k]>c[j][i]+di[i][k]))
						c[j+(1<<(k-1))][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].x,&v[n].y,&ch);
		}
		set();
		distp();
		init();
		rez();
		ch=1<<30;
		for(i=1;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;
}