#include<stdio.h>
#define dim 131073
#define infinit 200000001
using namespace std;

long C[dim][20],n, D[20];

struct vector
{
	long x, y;
};

/*int distanta(vector X, vector Y)
{ int d;

	d = (X.x - Y.x)*(X.x - Y.x) + (X.y - Y.y)*(X.y - Y.y);
	return d;	
}*/

long min(int a, int b)
{
	if(a < b) return a;
	return b;
}


vector V[20],W[20];

int main()
{ long i,j,t,c,d,a,b,n1, b1, sol,putere;

	FILE *f = fopen("bibel.in", "r");
	FILE *g = fopen("bibel.out", "w");
	
  W[1].x = W[1].y = D[1] = 0;
  c = 0; n1 = 1; 
  //fscanf(f, "%ld", &c);
  while(c != 2)     //citirea din fisier
	{
	fscanf(f, "%ld", &c);
	if(c == 2) return 0;
	
	n = 0;
	while(c == 0)
		{
			n++;
			fscanf(f, "%ld%ld", &V[n].x, &V[n].y);
			fscanf(f, "%ld", &c);
		}
	 				
		
	  //while(c == 1)
	// {
	
	putere = (1<<n);
		//initializarea cu infinit
		for(i = 0; i < putere; i++)
			for(j = 1; j <= n; j++)
				C[i][j] = infinit;
		
		for(i = 1; i <= n1; i++)
			for(j = 1; j <= n; j++)
				{
					d = (W[i].x - V[j].x)*(W[i].x - V[j].x) + (W[i].y - V[j].y)*(W[i].y - V[j].y);
					C[(1<<(n-j))][j] = min(C[(1<<(n-j))][j], d + D[i]);
				}
		
		//a = i&(1<<(n-j));
		
		for(i = 0; i < putere; i++)
			for(j = 1; j <= n; j++)
				{a = (i&(1<<(n-j)));
				 if(a)
					for(t = 1; t <= n; t++)
					{
						b = (i&(1<<(n-t)));
						if(b == 0)
						{
							d = (V[j].x - V[t].x)*(V[j].x - V[t].x) + (V[j].y - V[t].y)*(V[j].y - V[t].y);
							b1 = (i|(1<<(n-t)));
							C[b1][t] = min(C[b1][t], C[i][j] + d);						
						}
					}
				}
		//min1 = min2 = infinit;
		sol = infinit; n1 = n;
		for(i = 1; i <= n; i++)
		{
			D[i] = C[putere-1][i];
			W[i].x = V[i].x;
			W[i].y = V[i].y;
			
			/*for(j = 1; j <= (1<<n); j++)
			{
				if(C[i][j] != min1) sol += C[i][j];
				
				//if(C[i][j] < min1) min2 = min1, min1 = C[i][j];
				// else if(C[i][j] < min2) min2 = C[i][j];
				//n1 = n;
			}*/
			
			if(sol > C[putere-1][i]) sol = C[putere-1][i];
			//n1 = n;		
		}
	 
	 fprintf(g, "%ld\n", sol);  
	 
	 }
    //}	  
	fclose(f);
	fclose(g);
	return 0;
}