#include <fstream>
#include <cstring>
using namespace std;
ifstream in("bibel.in");
ofstream out("bibel.out");
int n,k=1,l[131072][18],m[20][20],d[20],c;
struct bibel
{ int x,y;
}a[21],b[21];
int distanta(bibel p1,bibel p2)
{ return (p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y);
}
int main()
{ in>>c;
  while(c!=2)
  { while(c==0)
    { n++;
      in>>a[n-1].x>>a[n-1].y>>c;
    }
    for(int i=0;i<(131072);i++)
      for(int j=0;j<=17;j++)
        l[i][j]=1073741823;
    for(int i=0;i<n;i++)
      for(int j=0;j<n;j++)
        m[i][j]=distanta(a[i],a[j]);
    for(int i=0;i<k;i++)
      for(int j=0;j<n;j++)
        if(l[1<<j][j]>d[i]+distanta(b[i],a[j]))
           l[1<<j][j]=d[i]+distanta(b[i],a[j]);
    for(int j=0;j<(1<<n);j++)
      for(int i=0;i<n;i++)
        if(j&(1<<i))
           for(k=0;k<n;k++)
             if(((j&(1<<k))==0) && (l[j+(1<<k)][k]>l[j][i]+m[i][k]))
                l[j+(1<<k)][k]=l[j][i]+m[i][k];
    c=1073741824;
    for(int i=0;i<n;i++)
    { d[i]=l[(1<<n)-1][i];
      if(c>d[i])
         c=d[i];
    }
    out<<c<<'\n';
    k=n;
    n=0;
    memcpy(b,a,sizeof(a));
    in>>c;
  }
  in.close();
  out.close();
  return 0;
}