#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)
#define LSB(x) (x^(x-1))&x

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

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

int main()
{
    freopen("bibel.in","r",stdin);
    freopen("bibel.out","w",stdout);
    
    int ch,i,j;
    
    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]));
            
        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;
}