#include <bits/stdc++.h>
using namespace std;
ifstream f("bibel.in");
ofstream g("bibel.out");
int n,N=1,i,j,k,val,D[20][20],d[20],c[1<<17][18];
struct pt
{
    int x,y;
}v[20],V[20];
int Dst(pt a,pt b)
{
    return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
}
int main()
{
    f>>val;
    while(val!=2)
    {
        while(!val)
        {
            f>>v[n].x>>v[n].y>>val;
            ++n;
        }
        for(i=0;i<(1<<17);++i)
            for(j=0;j<=17;++j) c[i][j]=1<<30;
        for(i=0;i<n;++i)
            for(j=0;j<n;++j) D[i][j]=Dst(v[i],v[j]);
        for(i=0;i<N;++i)
            for(j=0;j<n;++j)
                c[1<<j][j]=min(c[1<<j][j],d[i]+Dst(V[i],v[j]));
        for(j=0;j<(1<<n);++j)
            for(i=0;i<n;++i)
            if(j&(1<<i))
                for(k=0;k<n;++k)
                    if(!(j&(1<<k)))
                        c[j+(1<<k)][k]=min(c[j+(1<<k)][k],c[j][i]+D[i][k]);
        val=1<<30;
        for(i=0;i<n;++i)
        {
            d[i]=c[(1<<n)-1][i];
            val=min(val,d[i]);
        }
        g<<val<<'\n';
        N=n;
        n=0;
        memcpy(V,v,sizeof v);
        f>>val;
    }
    return 0;
}