#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;

vector<pair<int, int> > v;
int d[1 << 17][17];
vector<pair<int, int> > prrev;
vector<int> pp;

int main() {
    int i, j, k;
    freopen("bibel.in", "r", stdin);
    freopen("bibel.out", "w", stdout);
    pp.push_back(0);
    prrev.push_back(make_pair(0, 0));
    while(true) {
        int a;
        v.clear();
        while(true) {
            scanf("%d", &a);
            if(a != 0) {
                break;
            }
            int x, y;
            scanf("%d %d", &x, &y);
            v.push_back(make_pair(x, y));
        }
        if(a == 2) {
            break;
        }
        memset(d, sizeof(d), 0);
        for(i = 0; i < (1 << v.size()); i++) {
            for(j = 0; j < v.size(); j++) {
                if(i & (1 << j)) {
                    d[i][j] = 0;
                    for(k = 0; k < v.size(); k++) {
                        if((i & (1 << k)) && j != k) {
                            if(i ^ (1 << k) != 0 &&
                               (d[i][j] == 0 || d[i][j] > d[i ^ (1 << j)][k] + (v[j].first - v[k].first) * (v[j].first - v[k].first) + (v[j].second - v[k].second) * (v[j].second - v[k].second))) {
                                d[i][j] = d[i ^ (1 << j)][k] + (v[j].first - v[k].first) * (v[j].first - v[k].first) + (v[j].second - v[k].second) * (v[j].second - v[k].second);
                            }
                        }
                    }
                    if((i ^ (1 << j)) == 0) {
                        d[i][j] = pp[0] + (v[j].first - prrev[0].first) * (v[j].first - prrev[0].first) + (v[j].second - prrev[0].second) * (v[j].second - prrev[0].second);
                        for(k = 1; k < prrev.size(); k++) {
                            int crt = pp[k] + (v[j].first - prrev[k].first) * (v[j].first - prrev[k].first) + (v[j].second - prrev[k].second) * (v[j].second - prrev[k].second);
                            if(crt < d[i][j]) {
                                d[i][j] = crt;
                            }
                        }
                    }
                }
            }
        }
        int mx = 1 << 30;
        prrev.clear();
        pp.clear();
        for(i = 0; i < v.size(); i++) {
            if(mx > d[(1 << v.size()) - 1][i] && d[(1 << v.size()) - 1][i] != 0) {
                mx = d[(1 << v.size()) - 1][i];
            }
            pp.push_back(d[(1 << v.size()) - 1][i]);
            prrev.push_back(v[i]);
        }
        printf("%d\n", mx);
    }
    return 0;
}