#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=2147480000;
    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]>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)
            if ((i>>j)%2)
                for (k=0;k<n;++k)
                    if (((i>>k)%2==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=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]=2147480000;
    n2=n;
    printf("%d\n",min);
}

int main()
{
    int i,j;
    freopen("bibel.in","r",stdin);
    freopen("bibel.out","w",stdout);
    for (i=0;i<(1<<17)-1;++i)
        for (j=0;j<17;++j)
            d[i][j]=2147480000;
    while (x!=2) table();
    return 0;
}