#include <cstdio>
#define maxn 20
#define maxx 1<<18
#include <vector>
#include <cmath>
#define inf 0x3f3f3f3f
#include <algorithm>
#include <cstring>

using namespace std;

int C[maxx][maxn],cost[maxn][maxn];
vector <pair<int,int> > V;

int calc(int,int);

int main(){
    freopen("bibel.in","r",stdin);
    freopen("bibel.out","w",stdout);
    int x,y,z,S;
    size_t t=0;
    V.push_back(make_pair(0,0));
    while(true){
        scanf("%d",&x);
        if(x == 2)break;
        while(x==0){
            scanf("%d %d ",&y,&z);
            V.push_back(make_pair(y,z));
            scanf("%d",&x);
        }

        S = inf;
        memset(C,-1,sizeof(C));
        for(size_t i = 0;i < V.size();++i)C[1][i] = 0;

        for(size_t i = 0;i < V.size();++i)
            for(size_t j = i;j < V.size();++j)cost[j][i] = cost[i][j] = pow(V[i].first-V[j].first,2) + pow(V[i].second-V[j].second,2);

        for(size_t i = 0;i < V.size();++i){

            S = min(S,calc((1<<V.size())-1,i) + cost[i][0]);
        }

        printf("%d\n",S);


    }
    return 0;
}
int calc(int conf,int nod){
    if(C[conf][nod] == -1){
        C[conf][nod] = inf;
        for(size_t i = 0;i < V.size();++i){
            if(conf & (1<<i))  ///ma asigur ca nodul se afla in lant
                if(i != 0 || conf == (1<<nod)+1)
                  C[conf][nod] = min(C[conf][nod],calc(conf ^ (1 << nod),i) + cost[i][nod]);
        }
    }
    return C[conf][nod];
}