#include <stdio.h>

int v[2][17],v2[2][17],p[17],n,nn,n2=1,d[132000][17],x;

inline int dist(int i,int j)
{
    return (v[0][j]-v[0][i])*(v[0][j]-v[0][i])+(v[1][j]-v[1][i])*(v[1][j]-v[1][i]);
}

void table()
{
    int i=0,j,k,min=0;
    scanf("%d",&x);
    if (x==2) return;
    while (!x)
    {
        scanf("%d%d%d",&v[0][i],&v[1][i],&x);
        ++i;
    }
    n=i;
    nn=1<<n;
    for (i=0;i<n;++i)
        for (j=0;j<n2;++j)
            if ((d[1<<i][i]==0)||(d[1<<i][i]>p[j]+(v[0][i]-v2[0][j])*(v[0][i]-v2[0][j])+(v[1][i]-v2[1][j])*(v[1][i]-v2[1][j])))
                d[1<<i][i]=p[j]+(v[0][i]-v2[0][j])*(v[0][i]-v2[0][j])+(v[1][i]-v2[1][j])*(v[1][i]-v2[1][j]);
    for (i=1;i<nn-1;++i)
        for (j=0;j<n;++j)
            for (k=0;k<n;++k)
                if (((i>>j)%2)&&((i>>k)%2==0)&&((d[i+(1<<k)][k]==0)||(d[i+(1<<k)][k]>d[i][j]+dist(j,k))))
                    d[i+(1<<k)][k]=d[i][j]+dist(j,k);
    for (i=0;i<n;++i)
    {
        p[i]=d[nn-1][i];
        if ((p[i]<min)||(min==0)) min=p[i];
        v2[0][i]=v[0][i];
        v2[1][i]=v[1][i];
    }
    for (i=0;i<nn;++i)
        for (j=0;j<n;++j)
            d[i][j]=0;
    n2=n;
    printf("%d\n",min);
}

int main()
{
    freopen("bibel.in","r",stdin);
    freopen("bibel.out","w",stdout);
    while (x!=2) table();
    return 0;
}