#include <fstream>
#include <algorithm>
#define inf 1<<30
#define kmax 16
using namespace std;
ifstream f("bibel.in");
ofstream g("bibel.out");
int a,b,xv[25],yv[25],n1,x[25],y[25],n;
int v[1<<(kmax+1)][kmax+1];
int 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;
    n=-1;
    for (;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<=n1;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=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] + dist(x[k],y[k],x[j],y[j]));

    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];
    }
    n1=n;
    g<<sol<<'\n';
}
int main()
{
    int t;
    xv[0]=0;yv[0]=0;
    n1=0;
    f>>t;
    for (;t-2;) {
        if (t==1)
            f>>t;
        solve(t);
        f>>t;
    }
    return 0;
}