#include <cstdio>
#define inf 2147483647 
#define min(a,b) (a < b ? a : b)  

using namespace std;

struct poz {long x; long y;};

long v[134078][20];

long dist(poz a, poz b)
    {
    long rez=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    return rez;    
    }
    

int main(){
long n,a,b,nrt,cs[20],i,j,k,rez,p,put[20];
poz t[20],x[20];
freopen("bibel.in","r",stdin);
freopen("bibel.out","w",stdout);
for (i=0;i<=20;i++)
    put[i]=1<<i;
nrt=1;
t[1].x=0;t[1].y=0;cs[1]=0;
a=0;
while (a!=2)
    {
    scanf("%d",&a);
    if (a==2)
        return 0;    
    n=0;
    while (a!=1)
        {
        n++;
        scanf("%d%d",&x[n].x,&x[n].y);
        scanf("%d",&a);
        }    
    p=1<<n;
    for (i=0;i<=p;i++)
        for (j=1;j<=n;j++)
            v[i][j]=inf;
    for(i=1;i<=nrt;i++)
        for (j=1;j<=n;j++)
            v[put[n-j]][j]=min(dist(t[i],x[j])+cs[i],v[put[n-j]][j]);        
    for (j=0;j<p;j++)
        for (i=1;i<=n;i++)
            //verific daca i-ul mi-e continut in configuratia asta
            if ((put[n-i])&j)
                for (k=1;k<=n;++k)
                    //am configuratia j cu ultimu luat fiind i si avansez 
                    //in configuratiile urmatoare adica merg de la i la k
                    if (((put[n-k])&j)==0)    
                        v[j|(put[n-k])][k]=min(v[j|(put[n-k])][k],v[j][i]+dist(x[i],x[k]));
    rez=inf;nrt=n;
    for (i=1;i<=n;i++)
        {
        cs[i]=v[p-1][i];
        t[i].x=x[i].x;t[i].y=x[i].y;
        if (v[p-1][i]<rez)
            rez=v[p-1][i];
        }    
    printf("%ld\n",rez);
    }
return 0;
}