#include <stdio.h>

#define maxn 17
#define maxx 131072
#define inf 2147483647
#define dist(x1,y1,x2,y2) (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)
#define min(a,b) (a < b ? a : b)

int n,m;
int c[maxn][maxx];
int d[maxn],sol;
int lx[maxn],ly[maxn],x[maxn],y[maxn];

int main()
{
    freopen("bibel.in","r",stdin);
    freopen("bibel.out","w",stdout);
    
    int ch,i,j,k;
    
    m = 1;
    
    while (1)
    {
        scanf("%d ",&ch);
        if (ch==2) return 0;
        n=0;
        while (ch!=1)
        {
            scanf("%d %d ",&x[n],&y[n]);
            n++;
            scanf("%d ",&ch);
        }
        
        for (i=0;i<n;++i)
            for (j=0;j<1<<n;++j) c[i][j] = inf;
        
        for (i=0;i<m;++i) 
            for (j=0;j<n;++j) 
                if (d[i] + dist(lx[i],ly[i],x[j],y[j]) < c[j][1<<j]) c[j][1<<j] = d[i] + dist(lx[i],ly[i],x[j],y[j]);
            
        for (i=0;i<1<<n;++i)
            for (j=0;j<n;++j)
                if (i&(1<<j)) 
                    for (k=0;k<n;++k) 
                        if ((i&(1<<k))==0 && c[j][i] + dist(x[j],y[j],x[k],y[k]) < c[k][i+(1<<k)]) c[k][i+(1<<k)] = c[j][i] + dist(x[j],y[j],x[k],y[k]);
            
        sol = inf;
                
        for (i=0;i<n;++i) 
        {
            d[i] = c[i][(1<<n)-1];
            sol = min(sol, d[i]);
        }
        
        printf("%d\n",sol);
        
        for (i=0;i<n;++i) lx[i] = x[i], ly[i] = y[i];
            
        m = n;
    }
    
    return 0;
}