#include <bits/stdc++.h>

using namespace std;

const int MAXN = 17;
const int INF = 2e9;

int dp[1 << MAXN][MAXN];
int dst[MAXN][MAXN];
vector <pair <int, int>> v, w;

int main()
{
    int stp = 1, test = 0, lstn, lstans;
    FILE *fin = fopen("bibel.in", "r"), *fout = fopen("bibel.out", "w");
    fscanf(fin, "%d", &stp);
    v.resize(MAXN);
    w.resize(MAXN);
    while (stp != 2) {
      ++test;
      int x, y, n = 0;
      while (stp == 0) {
        fscanf(fin, "%d%d%d", &x, &y, &stp);
        v[n++] = make_pair(x, y);
      }
      for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
          dst[i][j] = (v[i].first - v[j].first) * (v[i].first - v[j].first) + (v[i].second - v[j].second) * (v[i].second - v[j].second);
      if (test == 1) {
        for (int conf = 0; conf < (1 << n); ++conf)
          for (int i = 0; i < n; ++i)
            dp[conf][i] = INF;
        for (int i = 0; i < n; ++i)
          dp[1 << i][i] = v[i].first * v[i].first + v[i].second * v[i].second;
      } else {
        for (int i = 0; i < n; ++i) {
          dp[1 << i][i] = INF;
          for (int j = 0; j < lstn; ++j)
            dp[1 << i][i] = min(dp[1 << i][i], dp[(1 << lstn) - 1][j] + (w[j].first - v[i].first) * (w[j].first - v[i].first) + (w[j].second - v[i].second) * (w[j].second - v[i].second));
        }
        for (int conf = 0; conf < n; ++conf)
          if (conf & (conf - 1))
            for (int i = 0; i < n; ++i)
              dp[conf][i] = INF;
      }
      for (int conf = 3; conf < (1 << n); ++conf)
        if (conf & (conf - 1))
          for (int i = 0; i < n; ++i)
            if ((1 << i) & conf) {
              int mini = INF;
              for (int j = 0; j < n; ++j)
                if (i != j && (conf & (1 << j)))
                  mini = min(mini, dp[conf ^ (1 << i)][j] + dst[i][j]);
              dp[conf][i] = mini;
            }
      int ans = INF;
      for (int i = 0; i < n; ++i)
        ans = min(ans, dp[(1 << n) - 1][i]);
      if (n == 0)
        ans = lstans;
      else {
        w = v;
        lstn = n;
        lstans = ans;
      }
      fprintf(fout, "%d\n", ans);
      fscanf(fin, "%d", &stp);
    }
    fclose(fin);
    fclose(fout);
    return 0;
}