#include<stdio.h>
const int nr=1000000000;
int i,j,k,l,n,m,car,d[131075][18],sol,b[18],p=1,dis[18][18];
struct cord
{
    int i,j;
};
int dist(int x1,int y1,int x2,int y2)
{
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
cord v[20],a[20];
int main()
{
    freopen("bibel.in","r",stdin);
    freopen("bibel.out","w",stdout);
    while(car!=2)
    {
        k=0;
        scanf("%d",&car);
        if(car==2)break;
        while(car!=1)
        {
            scanf("%d%d",&v[k].i,&v[k].j);
            scanf("%d",&car);
            ++k;
        }
        for(i=0;i<(1<<k);++i)
            for(j=0;j<k;++j)
            d[i][j]=nr;
        for(i=0;i<k;++i)
            for(j=0;j<p;++j)
            if(b[j]+dist(a[j].i,a[j].j,v[i].i,v[i].j)<d[(1<<i)][i])
            d[(1<<i)][i]=b[j]+dist(a[j].i,a[j].j,v[i].i,v[i].j);
        for(i=0;i<k;++i)
            for(j=0;j<k;++j)
            dis[i][j]=dist(v[i].i,v[i].j,v[j].i,v[j].j);
        for(i=0;i<(1<<k);++i)
            for(j=0;j<k;++j)
                if(i&(1<<j))
                    for(l=0;l<k;++l)
                        if((i&(1<<l))==0)
                            if(d[i][j]+dis[j][l]<d[i+(1<<l)][l])
                            d[i+(1<<(l))][l]=d[i][j]+dis[j][l];
        sol=nr;
        for(i=0;i<k;++i)
        {
            if(d[(1<<k)-1][i]<sol)
            sol=d[(1<<k)-1][i];
            b[i]=d[(1<<k)-1][i];
            a[i].i=v[i].i;
            a[i].j=v[i].j;
            p=k;
        }
        printf("%d\n",sol);
    }
    return 0;
}