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

long C[1<<17][20],n, D[20];
int puteri[20] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 924288};

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;	
}*/

int 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");
	
	
	//for(i = 0; i < 20; i++)
		//puteri[i] = (1<<i);	
	
	
  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[puteri[n-j]][j] = min(C[puteri[n-j]][j], (W[i].x - V[j].x)*(W[i].x - V[j].x) + (W[i].y - V[j].y)*(W[i].y - V[j].y) + D[i]);
				//}
		
		//a = i&(1<<(n-j));
		
		for(i = 0; i < putere; i++)
			for(j = 1; j <= n; j++)
				//{a = (i&(puteri[n-j]));
				 if(i&(puteri[n-j]))
					for(t = 1; t <= n; t++)
					//{
						//b = (i&(puteri[n-t]));
						if((i&(puteri[n-t])) == 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|(puteri[n-t]));
							C[i|(puteri[n-t])][t] = min(C[i|(puteri[n-t])][t], C[i][j] + (V[j].x - V[t].x)*(V[j].x - V[t].x) + (V[j].y - V[t].y)*(V[j].y - V[t].y));						
						//}
					//}
				//}
		//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;
}