#include <fstream>
#include <vector>
#define INF 0x3f3f3f3f
using namespace std;

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

using VI = vector<int>;
using VVI = vector<VI>;

int tip;

void Solve();

int main()
{
    while ( tip != 2 )
        Solve();
    is.close();
    os.close();
    return 0;
}

void Solve()
{
    is >> tip;
    if ( tip == 2 )
        return;
    int n = 1, x[18], y[18];
    x[0] = y[0] = 0;
    while ( !tip )
    {
        is >> x[n] >> y[n] >> tip;
        ++n;
    }
    VVI c(n, VI(n));
    for ( int i = 0; i < n - 1; ++i )
        for ( int j = i + 1; j < n; ++j )
            c[i][j] = c[j][i] = ( x[i] - x[j] ) * ( x[i] - x[j] ) +
                                ( y[i] - y[j] ) * ( y[i] - y[j] );
    VVI q(1 << n, VI(n, INF));
    q[1][0] = 0;
    for ( int k = 1; k < 1 << n; ++k )
        for ( int i = 0; i < n; ++i )
            if ( k & (1 << i) && q[k][i] != INF )
                for ( int j = 0; j < n; ++j )
                    if ( !( k & (1 << j)) )
                        q[k | (1 << j)][j] = min(q[k | (1 << j)][j], q[k][i] + c[i][j]);
    int answ = INF;
    for ( int i = 0; i < n; ++i )
        answ = min(answ, q[(1 << n) - 1][i]);
    os << answ << "\n";
}