#include <bits/stdc++.h>
using namespace std;
ifstream fin("bibel.in");
ofstream fout("bibel.out");
int n,N=1,i,j,k,val,D[20][20],d[20],c[1<<17][18];
//c[i][j] - costul de a ridica bilele din configuratia binara a lui i ultima ridicata fiind j
const int INF = 1 << 30;


struct Punct
{
    int x,y;
}v[20],V[20];
int Dst(Punct a, Punct b)
{
    //distanti dintre doua bile
    return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
}
int main()
{
    fin >> val;
    while(val!=2)
    {
        while(!val)
        {
            fin >> v[n].x >> v[n].y >> val;
            ++n;
        }
        for(i=0;i<(1<<17);++i)
        {
            for(j=0;j<=17;++j)
            {
                c[i][j]=INF;
            }
        }
        for(i=0;i<n;++i)
        {
            for(j=0;j<n;++j)
            {
                //distanta de la bila i la bila j
                D[i][j]=Dst(v[i],v[j]);
            }
        }

        for(i=0;i<N;++i)
        {
            for(j=0;j<n;++j)
            {
                //disttanta minima la o bila din nivelul anterior la o bila j din acest nivel
                c[1<<j][j] = min(c[1<<j][j],d[i]+Dst(V[i],v[j]));
            }
        }


        for(j=0;j<(1<<n);++j)//starea curenta
        {
             for(i=0;i<n;++i)//ultima bila ridicata
             {
                 if(j&(1<<i))
                 {
                      for(k=0;k<n;++k) // urmatoarea alegere
                      {
                           if(!(j&(1<<k)))
                                c[j+(1<<k)][k]=min(c[j+(1<<k)][k],c[j][i]+D[i][k]);
                      }
                 }
             }

        }

        int sol = INF;
        for(i=0;i<n;++i)
        {
            d[i] = c[(1<<n)-1][i];
            sol = min(sol, d[i]);
        }
        fout << sol <<'\n';
        N=n;
        n=0;
        for(i = 0; i < N; i++)
        {
            V[i] = v[i];
        }
        //memcpy(V,v,sizeof v);
        fin >> val;
    }
    return 0;
}