#include<fstream>
#define ll long long
using namespace std;

ll dist(int x1, int y1, int x2, int y2){
	return 1LL * (x1-x2) * (x1-x2) + 1LL * (y1-y2) * (y1-y2);
}

ll d[20][20], SUM, SCurrent[20], Slast[20], SL;
int N, st[20];
int x[20], y[20], x2[20], y2[20];
int lastx = 0, lasty = 0;
bool viz[20];
ll costm[20], Nlast = 1;

void back(int k){
	
	if(k == N+1)
	{
		ll Sum2 = 0;
		for(int i=0;i<N;++i)
		{
			Sum2 += d[st[i]][st[i+1]];
		}
		
		if(Sum2 + SL < SCurrent[st[N]] || SCurrent[st[N]] == -1) 
		{
			SCurrent[st[N]] = Sum2 + SL;
			lastx = x[st[N]];
			lasty = y[st[N]];
		}
		
		return ;
	}
	
	for(int i = 1;i<=N; ++i)
	  if(!viz[i])
	  {
	  	viz[i] = 1;
	  	st[k] = i;
	  	back(k+1);
	  	viz[i] = 0;
	  }	
}

int main(){
	ifstream cin("bibel.in");
	ofstream cout("bibel.out");
	int cod,i,j;
	
	
	do
	{
		N = 0;

		cin >> cod;
		
		if(cod == 2) continue;
		
		while(cod != 1)
		{
			++N;
			cin >> x[N] >> y[N] >> cod;				
		}
				
		for(i=1;i<N;++i)
		  for(j=i+1;j<=N;++j)
	      {
	      	d[i][j] = d[j][i] = dist(x[i], y[i], x[j], y[j]);
	      }
		
		for(i=1;i<=N;++i) SCurrent[i] = -1;
		
		for(i=1;i<=Nlast;++i)
		{
			SL = Slast[i];
			x[0] = x2[i];
			y[0] = y2[i];
			
			for(j=1;j<=N;++j) d[0][j] = d[j][0]	 = dist(x[0], y[0], x[j], y[j]);
				
			back(1);
		}
		
		SUM = SCurrent[1];
		for(i=2;i<=N;++i) 
		  if(SCurrent[i] < SUM) SUM = SCurrent[i];
		
		cout << SUM << '\n';
		
		Nlast = N;
		for(i=1;i<=N;++i)
		{
			x2[i] = x[i];
			y2[i] = y[i];
			Slast[i] = SCurrent[i];
		}
		
	}while(cod != 2);
	
	
	
	return 0;
}