#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];
char v[maxx];

int main()
{
    freopen("bibel.in","r",stdin);
    freopen("bibel.out","w",stdout);
    
    int ch,i,j,k;
    
    m = 1;
    
    for (i=0;i<maxn;i++) v[1<<i] = i;
    
    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++) c[j][1<<j] = min(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[k][i+(1<<k)] = min(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;
}