#include <bits/stdc++.h>

using namespace std;

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

const int N = 100, M = 18, INF32 = 0x3f3f3f3f;
int tip, x, y, n, dp[N][M][1 << M], m[N], ans = INF32, d[M][M];
vector<pair<int, int>> nivel[N];

inline int dist(pair<int, int> a, pair<int, int> b){
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

int main(){
    while(f >> tip){
        if(tip == 0){
            f >> x >> y;
            nivel[n].push_back({x, y});
            m[n]++;
        }else if(tip == 1)
            n++;
        else
            break;
    }

    f.close();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m[i]; j++){
            for(int k = 1; k < 1 << m[i]; k++){
                dp[i][j][k] = INF32;
            }
        }
    }

    for(int j = 0; j < m[0]; j++)
        dp[0][j][1 << j] = dist({0, 0}, nivel[0][j]); // setam valorile initiale (timpul pt. a parcurge dist. de la poz. initiala (0, 0) la punctele din primul nivel)

    for(int i = 0; i < n; i++){
        if(i){ // dist. de la bilele din nivelul anterior la cele din nivelul curent
            for(int j = 0; j < m[i - 1]; j++){
                for(int k = 0; k < m[i]; k++){
                    dp[i][k][1 << k] = min(dp[i][k][1 << k], dp[i - 1][j][(1 << m[i]) - 1] + dist(nivel[i - 1][j], nivel[i][k]));
                }
            }
        }

        for(int k = 0; k < m[i]; k++){ // precalculam dist. dintre punctele din nivelul curent
            for(int t = 0; t < m[i]; t++){
                d[k][t] = dist(nivel[i][k], nivel[i][t]);
            }
        }

        for(int j = 1; j < 1 << m[i]; j++){
            for(int k = 0; k < m[i]; k++){
                if(j & (1 << k)){
                    for(int t = 0; t < m[i]; t++){
                        if(j & (1 << t))
                            continue;

                        dp[i][t][j + (1 << t)] = min(dp[i][t][j + (1 << t)], dp[i][k][j] + d[k][t]);
                    }
                }
            }
        }

        for(int k = 0; k < m[i]; k++)
            ans = min(ans, dp[i][k][(1 << m[i]) - 1]);

        g << ans << '\n';
        ans = INF32;
    }

    g.close();
}