#include<fstream>
#include<algorithm>
#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];
bool viz[20];
ll costm[20], Nlast = 1;
ll CMinStart[20], CMinFinish[20], CMinFinishLast[20], CMinFinishLast2[20];

void back(int k){
	
	if(k == N+1)
	{
		ll Sum2 = 0, SS2 = 20000000000LL;
		for(int i=1;i<N;++i)
		  Sum2 += d[st[i]][st[i+1]];
		
		for(int i = 1; i<= Nlast; ++i)
		  if(CMinFinishLast[i] + Sum2 + dist(x2[i], y2[i], x[st[1]], y[st[1]]) <= SS2) 
		    SS2 = CMinFinishLast[i] + Sum2 + dist(x2[i], y2[i], x[st[1]], y[st[1]]);
		
		CMinStart[st[1]] = min(Sum2, CMinStart[st[1]]);
		CMinFinish[st[N]] = min(CMinFinish[st[N]], SS2);
	
		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;
	ll SS;
	
	Nlast = 1;
	
	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) CMinStart[i] = CMinFinish[i] = 2000000000;
		
		back(1);
		
		SS = 20000000000LL;
		for(i=1;i<=N;++i) CMinFinishLast2[i] = 20000000000LL;

		for(i=1;i<=N;++i)
		  SS = min(SS, CMinFinish[i]);
		
		cout << SS << '\n';
		
		Nlast = N;
		for(i=1;i<=N;++i)
		{
			x2[i] = x[i];
			y2[i] = y[i];
			CMinFinishLast[i] = CMinFinish[i];
		}
		
	}while(cod != 2);
	
	
	
	return 0;
}