#include<stdio.h>
#include<algorithm>
const int nr=1000000000;
using namespace std;
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++)
            d[(1<<i)][i]=min(b[j]+dist(a[j].i,a[j].j,v[i].i,v[i].j),d[(1<<i)][i]);
        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)
                            d[i+(1<<(l))][l]=min(d[i+(1<<(l))][l],d[i][j]+dis[j][l]);
        sol=nr;
        for(i=0;i<k;i++)
        {
            sol=min(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;
}