#include<cstdio>
using namespace std;

const int nMax = 18;
const int INF = 1999999999;

int C[1 << nMax][nMax];
struct punct{int x, y;}v1[nMax], v2[nMax];
int s[nMax];

int nre;

inline int minim (int a, int b){
    return a < b ? a : b;
}

int getTime(punct a, punct b){
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

int main(){
    FILE *in = fopen("bibel.in","r");
    FILE *out = fopen("bibel.out","w");

    int cod, n, i, j, k, n2 = 1;
    int bst;

    fscanf(in,"%d", &cod);

    while(cod != 2){
        nre = 0;
        while(cod != 1){
            fscanf(in,"%d%d", &v1[nre].x, &v1[nre].y);
            fscanf(in,"%d", &cod);
            ++nre;
        }

        n = nre;
        for( i = 0 ; i < (1 << n) ; ++i)
            for( j = 0 ; j < n ; ++j)
                C[i][j] = INF;

        for(i = 0 ; i < n ; ++i){
            for(j = 0 ; j < n2 ; ++j){
                C[1 << i][i] = minim(C[1 << i][i], s[j] + getTime(v1[i], v2[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(j != k && i & (1 << k)){
                            C[i][j] = minim(C[i][j], C[i ^ (1 << j)][k] + getTime(v1[k], v1[j]));
                        }
                    }
                }
            }
        }

        bst = INF;
        for( i = 1 ; i < n ; ++i){
            bst = minim(bst, C[(1 << n) - 1][i]);
            v2[i].x = v1[i].x;
            v2[i].y = v1[i].y;
            s[i] = C[(1 << n) - 1][i];
        }
        n2 = n;
        fprintf(out, "%d\n", bst);
        fscanf(in,"%d", &cod);
    }

    return 0;
}