#include<stdio.h>
#include<string.h>
struct point
{int x,y;};
int n,n1=1,c[1<<17][18],di[20][20],d[20];
point v[20],v1[20];
inline int dist(point p1, point p2)
{return (p2.x-p1.x)+(p2.x-p1.x)+(p2.y-p1.y)+(p2.y-p1.y);}
int main()
{freopen("bibel.in","r",stdin);
freopen("bibel.out","w",stdout);
int ch,i,j,k;
scanf("%d",&ch);
while(ch!=2)
   {while(ch==0)
	  {n++;
	  scanf("%d%d%d",&v[n-1].x,&v[n-1].y,&ch);}
  for(i=0;i<(1<<17);i++)
    for(j=0;j<=17;j++)
	  c[i][j]=(1<<30)-1;
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      di[i][j]=dist(v[i],v[j]);
  for(i=0;i<n1;i++)
    for(j=0;j<n;j++)
      if(c[1<<j][j]>d[i]+dist(v1[i],v[j]))
	   c[1<<j][j]=d[i]+dist(v1[i],v[j]);
  for(j=0;j<(1<<n);j++)
    for(i=0;i<n;i++)
	  if(j&(1<<i))
	   for(k=0;k<n;k++)
	     if(((j&(1<<k))==0) && (c[j+(1<<k)][k]>c[j][i]+di[i][k]))
	      c[j+(1<<k)][k]=c[j][i]+di[i][k];
   ch=1<<30;
   for(i=0;i<n;i++)
     {d[i]=c[(1<<n)-1][i];
	 if(ch>d[i])
	  ch=d[i];}
   printf("%d\n",ch);
   n1=n;
   n=0;
   memcpy(v1,v,sizeof(v));
   scanf("%d",&ch);}
return 0;}