#include<fstream>
#include<iostream>

using namespace std;

ifstream in("bibel.in");
ofstream out("bibel.out");

const int INF = 1000000000;
const int DIM = 100000;

struct Data{
  int l;
  int c;
};

int dp[1<<17][20], v[20],  y[20], n, res, a, nl, x, poz;
Data z1[20],z2[20];
char buff[DIM];

int read(){
  int nr = 0;

  while(!isdigit(buff[poz]))
    if(++poz == DIM){
      in.read(buff, DIM);
      poz = 0;
    }

  while(isdigit(buff[poz])){
    nr = nr * 10 + (buff[poz] - '0');

    if(++poz == DIM){
      in.read(buff, DIM);
      poz = 0;
    }
  }

  return nr;
}

inline int dist(Data a, Data b){
  int x = a.l - b.l;
  int y = a.c - b.c;

  return x * x + y * y;
}

void solve(){
  for(int i = 1; i <= nl; ++i)
    for(int j = 1;j <= n; ++j)
      dp[v[n - j]][j] = min(dist(z2[i], z1[j]) + y[i], dp[v[n - j]][j]);
  for(int i = 0; i < x; i++)
    for(int j = 1;j <= n; j++)
      if(((v[n - j]) & i))
        for(int k = 1;k <= n; ++k)
          if(((v[n - k] & i)) == 0)
            dp[(i | (v[n - k]))][k]=min(dp[(i|v[n - k])][k], dp[i][j] + dist(z1[j], z1[k]));
}

void pfinal(){
  res = INF;
  nl = n;
  for(int i = 1; i <= n; i++){
    y[i] = dp[x - 1][i];
    z2[i].l = z1[i].l;
    z2[i].c = z1[i].c;
    if(dp[x - 1][i] < res)
      res = dp[x - 1][i];
  }
  out << res << '\n';
}

void init(){
  x = (1 << n);
  for(int i = 0; i < x; i++)
    for(int j = 1; j <= n; j++)
      dp[i][j] = INF;
}

int main()
{
  for(int i = 0; i < 20; i++)
    v[i] = (1 << i);
  nl=1;

  while (a!=2){
    //in >> a;
    a = read();
    if (a == 2)
      return 0;
    n = 0;
    while (a != 1){
      n++;
      //in >> z1[n].l >> z1[n].c >> a;
      z1[n].l = read();
      z1[n].c = read();
      a = read();
    }
    init();
    solve();
    pfinal();
  }

  in.close();
  out.close();
  return 0;
}