#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
FILE*fin=fopen("bibel.in","r");
FILE*fout=fopen("bibel.out","w");
#define bm 20
#define inf 2000000000
int x[2][bm],y[2][bm],ba=1,bc,old=0,nw=1;
int p2[30],ans[140000][bm],best[bm];
inline int dist(int a,int wa,int b,int wb)
{
    return (x[wa][a]-x[wb][b])*(x[wa][a]-x[wb][b])+(y[wa][a]-y[wb][b])*(y[wa][a]-y[wb][b]);
}
inline void solve()
{
  int i,val,j,config,nconfig,bb;
  for(i=1;i<=bc;i++)
  {
    val=inf;
    for(j=1;j<=ba;j++)
      if(best[j]+dist(j,old,i,nw)<val)
        val=best[j]+dist(j,old,i,nw);
    ans[p2[i-1]][i]=val;    
  }  
  for(config=2;config<p2[bc];config++)
    for(i=1;i<=bc;i++)
    {
      val=inf;
      if((config&p2[i-1])&&(config-p2[i-1])) 
      {
        nconfig=config-p2[i-1];
        for(j=1;j<=bc;j++)
          if((nconfig&p2[j-1])&&(ans[nconfig][j]+dist(i,nw,j,nw))<val)
            val=ans[nconfig][j]+dist(i,nw,j,nw);
      }
      if(val!=inf) ans[config][i]=val;
    }  
  bb=inf;
  for(i=1;i<=bc;i++)
  {
    best[i]=ans[p2[bc]-1][i];
    if(best[i]<bb) bb=best[i];
  }    
  fprintf(fout,"%d\n",bb);
}
int main()
{
  int o,i;
  x[0][1]=0;y[0][1]=0;
  best[1]=0;
  p2[0]=1;
  for(i=1;i<=20;i++)
    p2[i]=p2[i-1]*2;
  fscanf(fin,"%d",&o);
  while(o<2)
  {
    bc=0;        
    while(!o)
    {
      bc++;;       
      fscanf(fin,"%d%d",&x[nw][bc],&y[nw][bc]);
      fscanf(fin,"%d",&o);
    }
    solve();
    ba=bc;
    nw=!nw;
    old=!old;
    if(o==2) return 0;
    else fscanf(fin,"%d",&o);
  }  
  fclose(fin);
  fclose(fout);  
  return 0;
}