#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];

inline int solve(int nod,int conf)
{
    if (c[nod][conf]==inf)
    {
        int i;
        for (i=0;i<n;i++)
            if (i!=nod && (conf&(1<<i))) c[nod][conf] = min(c[nod][conf], solve(i,conf-(1<<nod)) + dist(x[nod],y[nod],x[i],y[i]));
    }
    
    return c[nod][conf];
}

int main()
{
    freopen("bibel.in","r",stdin);
    freopen("bibel.out","w",stdout);
    
    int ch,i,j;
    
    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++) c[j][1<<j] = min(c[j][1<<j],d[i] + dist(lx[i],ly[i],x[j],y[j]));
            
        sol = inf;
                
        for (i=0;i<n;i++) 
        {
            d[i] = solve(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;
}