#include <cstdio>
#define inf 2147483647 

using namespace std;

struct poz {long x; long y;};

long long v[134078][20],n,a,b,nrt,cs[50],i,j,k,rez;
poz t[50],x[50];

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;    
    }
    
long min(long a, long b)
    {
    if (a<b)
        return a;
    else
        return b;    
    }

int main(){
freopen("bibel.in","r",stdin);
freopen("bibel.out","w",stdout);
nrt=1;
t[1].x=0;t[1].y=0;cs[1]=0;
while (n!=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);
        }    
    for (i=0;i<=1<<n;i++)
        for (j=1;j<=n;j++)
            v[i][j]=inf;
    for(i=1;i<=nrt;i++)
        for (j=1;j<=n;j++)
            v[1 << (n-j)][j]=min(dist(t[i],x[j])+cs[i],v[1<<(n-j)][j]);
    
    
/*    for (i=0;i<=1<<n;i++)
        {
        for (j=1;j<=n;j++)
            printf("%d ",v[i][j]);
        printf("\n");
        }   */ 
        
    for (j=0;j<(1<<n);j++)
        for (i=1;i<=n;i++)
            //verific daca i-ul mi-e continut in configuratia asta
            if ((1<<(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 (((1<<(n-k))&j)==0)    
                        v[j|(1<<(n-k))][k]=min(v[j|(1<<(n-k))][k],v[j][i]+dist(x[i],x[k]));
    rez=inf;nrt=n;
    for (i=1;i<=n;i++)
        {
        cs[i]=v[(1<<n)-1][i];
        t[i].x=x[i].x;t[i].y=x[i].y;
        if (v[(1<<n)-1][i]<rez)
            rez=v[(1<<n)-1][i];
        }    
        
        

    printf("%d\n",rez);
    }
return 0;
}