#include <fstream>
#include <algorithm>
#define inf (1LL<<32)-1
#define kmax 17
using namespace std;
ifstream f("bibel.in");
ofstream g("bibel.out");
int a,b,xv[25],yv[25],nv,x[25],y[25],n;
int d[kmax][kmax];
unsigned int v[1<<kmax][kmax],sol;

int dist(int x,int y,int z, int t)
{
    return (x-z)*(x-z)+(y-t)*(y-t);
}
void solve(int t)
{
    int i,j,k;
    for (n=-1;t-1;) {
        n++;
        f>>x[n]>>y[n];
        f>>t;
    }
    for (i=1;i<=(1<<(n+1));i++)
        for (j=0;j<=n;j++)
            v[i][j]=inf;

    for (k=0;k<=nv;k++)
        for (j=0;j<=n;j++)
            v[1<<j][j]=min(v[1<<j][j],v[0][k]+dist(xv[k],yv[k],x[j],y[j]));

    for (i=0;i<=n;i++)
        for (j=0;j<=n;j++)
            d[i][j]=dist(x[i],y[i],x[j],y[j]);

    for (i=1;i<(1<<(n+1))-1;i++)
        for (k=0;k<=n;k++)
                if (((i&(1<<k))!=0))
            for (j=0;j<=n;j++)
                if (k!=j) {
                    if ((i&(1<<j))==0)
                        v[i+(1<<j)][j]=min(v[i+(1<<j)][j],v[i][k]+d[j][k]);
                }

    sol=inf;
    for (i=0;i<=n;i++) {
        if (v[(1<<(n+1))-1][i]<sol)
            sol=v[(1<<(n+1))-1][i];
        xv[i]=x[i];
        yv[i]=y[i];
        v[0][i]=v[(1<<(n+1))-1][i];
    }
    nv=n;
    g<<sol<<'\n';
}
int main()
{
    int t;
    xv[0]=0;yv[0]=0;
    nv=0;
    f>>t;
    for (;t-2;) {
        if (t==1)
            f>>t;
        solve(t);
        f>>t;
    }
    return 0;
}