#include <fstream>
#include <cstring>
using namespace std;
ifstream in("bibel.in");
ofstream out("bibel.out");
int ch,n,k=1;
int c[1<<17][21];
int m[21][21];
int d[21];
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>>ch;
  while(ch!=2)
  { while(ch==0)
    { n++;
      in>>a[n-1].x>>a[n-1].y>>ch;
    }
    for(int i=0;i<(1<<17);i++)
      for(int j=0;j<=17;j++)
        c[i][j]=(1<<30)-1;
    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(c[1<<j][j]>d[i]+distanta(b[i],a[j]))
           c[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(int q=0;q<n;q++)
             if(((j&(1<<q))==0) && (c[j+(1<<q)][k]>c[j][i]+m[i][q]))
                c[j+(1<<q)][q]=c[j][i]+m[i][q];
    ch=1<<30;
    for(int i=0;i<n;i++)
    { d[i]=c[(1<<n)-1][i];
      if(ch>d[i])
         ch=d[i];
    }
    out<<ch<<'\n';
    k=n;
    n=0;
    memcpy(b,a,sizeof(a));
    in>>ch;
  }
  in.close();
  out.close();
  return 0;
}