#include<fstream.h>
#include<iostream.h>
#include<cstdio>
#define inf 999999999
#define min(a,b) (a < b ? a : b)
using namespace std;
struct poz 
	   {
	   	   long l,c;
		   } ;
poz x[20],t[20];

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


for(i=0;i<20;i++)
    				  pune[i]=1<<i;

numarture=1;
a=0;
t[1].l=0;
t[1].c=0;
y[1]=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);
		}
    p=1<<n;
	for(i=0;i<p;i++)
	for(j=1;j<=n;j++)
			mat[i][j]=inf;
	for(i=1;i<=numarture;++i)
		for(j=1;j<=n;++j)	
			mat[pune[n-j]][j]=min(dist(t[i],x[j])+y[i],mat[pune[n-j]][j]);
	for(i=0;i<p;i++)
		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]));		
	r=inf;numarture=n;
	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("%ld\n",r);
	}return 0;
}