#include<fstream>
#include<iostream>

using namespace std;

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

const int INF = 1000000000;

struct Data{
  int l;
  int c;
};

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

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;
    if (a == 2)
      return 0;
    n = 0;
    while (a != 1){
      n++;
      in >> z1[n].l >> z1[n].c >> a;
    }
    init();
    solve();
    pfinal();
  }

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