# include <cstdio>
# include <cstring>

const char *FIN = "bibel.in", *FOU = "bibel.out";
const int oo = 0x3f3f3f3f;

int rez[20], X[2][20], Y[2][20], dp[1 << 17][20];

inline int min (int a, int b) {
    return (a < b ? a : b);
}

inline int sq (int X) {
    return X * X ;
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    memset (rez, 0x3f, sizeof (rez));
    rez[1] = 0;
    for (int x = 0, cnt = 1, bit = 0, I = 1; ; cnt = bit, I ^= 1) {
        scanf ("%d", &x);
        if (x == 2) break ;
        for (scanf ("%d %d %d", X[I] + 1, Y[I] + 1, &x), bit = 1; ; scanf ("%d %d %d", X[I] + bit, Y[I] + bit, &x)) {
            if (x == 1) break ;
            ++bit;
        }
        for (int i = 1; i < 1 << bit; ++i) {
            for (int j = 1, k = 1; j <= i; j <<= 1, ++k) {
                if (i & j) {
                    dp[i][k] = oo;
                    if (j == i) {
                        for (int ii = 1; ii <= cnt; ++ii)
                            dp[i][k] = min (dp[i][k], rez[ii] + sq (X[I][k] - X[I ^ 1][ii]) + sq (Y[I][k] - Y[I ^ 1][ii]));
                    } else {
                        for (int ii = 1, jj = 1; ii <= i; ii <<= 1, ++jj)
                            if ((ii & i) && ii != j)
                                dp[i][k] = min (dp[i][k], dp[i ^ j][jj] + sq (X[I][k] - X[I][jj]) + sq (Y[I][k] - Y[I][jj]));
                    }
                }
            }
        }
        int solution = oo;
        for (int i = 1; i <= bit; ++i) {
            rez[i] = dp[(1 << bit) - 1][i];
            solution = min (solution, rez[i]);
        }
        printf ("%d\n", solution);
    }
}