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

using namespace std;

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

void Rezolva();

int main(){
    freopen("bibel.in","r",stdin);
    freopen("bibel.out","w",stdout);
    int x,y,z;
    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);
        }

        Rezolva();

        printf("%d\n",S);
        //V.clear();
    }
    return 0;
}
void Rezolva(){
        int i,j,conf;
        N = V.size();
        S = inf;
        memset(C,inf,sizeof(C));
        for(i = 0;i < N;++i)C[1<<i][i] = 0;

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

        for(conf = 1;conf<=(1<<N)-1;++conf){
           for(i = 0;i < N;++i){
              if(conf & (1<<i)){
                 for(j = 0;j < N;++j){
                    if((conf & (1<<j)) && i != j){
                       C[conf][i] = min(C[conf][i],C[conf ^ (1<<j)][j] + cost[j][i]);
                    }
                 }
              }
           }
        }

        for(i = 0;i < N;++i)S = min(S,C[(1<<N)-1][0]);
}