#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std ;

#define maxb 18
#define maxs ( 1 << 17 )
#define inf ( 1 << 15 )

struct punct
{
    int x, y ;
};

int n ;
int lim = 1 ;

int sol[maxs][maxb] ;

int distanta[maxb][maxb] ;
int d[maxb];

punct v[maxb], w[maxb] ;

int dist(punct P, punct Q)
{
    return ( P.x - Q.x ) * ( P.x - Q.x ) + ( P.y - Q.y ) * ( P.y - Q.y ) ;
}

void init_sol_inf()
{
    for(int i = 0; i < maxs; ++i )
        for(int j = 0; j <= 17; ++j )
            sol[i][j] = inf ;
}

void init_distanta()
{
    for(int i = 0; i < n; ++i )
        for(int j = 0;j < n; ++j )
            distanta[i][j] = dist( v[i], v[j] ) ;
}

void init_sol()
{
    for(int i = 0; i < lim; ++i )
        for(int j = 0; j < n; ++j )
                sol[ ( 1 << j ) ][j] = min( sol[ ( 1 << j ) ][j], d[i] + dist( w[i], v[j] ) ) ;
}

void rezolva()
{
    for(int j = 0; j < ( 1 << n ); ++j )
        for(int i = 0; i < n; ++i )
            if( j & ( 1 << i ) )
                for(int k = 0; k < n; ++k )
                    if( ( ( j & ( 1 << k ) ) == 0 ) && ( sol[ j + ( 1 << k ) ][k] > sol[j][i] + distanta[i][k] ) )
                        sol[ j + ( 1 << k ) ][k] = sol[j][i] + distanta[i][k] ;
}

int main()
{
    freopen("bibel.in", "r", stdin);
    freopen("bibel.out", "w", stdout);

    int nr ;

    scanf("%d", &nr);

    while( nr != 2 )
    {
        while( nr == 0 )
        {
            ++n ;
            scanf("%d%d%d", &v[n-1].x, &v[n-1].y, &nr);
        }

        init_sol_inf() ;

        init_distanta() ;

        init_sol() ;

        rezolva() ;

        nr = inf ;

        for(int i = 0; i < n; ++i )
        {
            d[i] = sol[ ( 1 << n ) - 1 ][i] ;

            nr = min( nr, d[i] ) ;
        }

        printf("%d\n", nr);

        lim = n ;
        n = 0 ;
        memcpy( w, v, sizeof( v ) ) ;

        scanf("%d", &nr);
    }

    return 0 ;

}