#include<fstream>
#include<algorithm>
const int INF = 0x3f3f3f3f;
using namespace std;

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

int N, Nlast, d[20][20];
int x[20], y[20], x2[20], y2[20];
int Vl[1<<20], a[1<<20][20];

int solve(){
	int i,j,k;
	
	for(i=0;i<N-1;++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=0;i<(1<<N);++i)
	  for(j=0;j<N;++j)
	    a[i][j] = INF;
	
	for(i=0;i<N;++i)
	  for(j=0;j<Nlast;++j)
	    a[1<<i][i] = min(a[1<<i][i], Vl[j] + dist(x2[j], y2[j], x[i], y[i]));
	
	for(i=0;i<(1<<N);++i)
	  for(j=0;j<N;++j)
	    if(i & (1<<j))
	      for(k=0;(i>>k);++k)
	        if(i & (1<<k) && (j != k))
	        a[i][j] = min(a[i][j], a[i^(1<<j)][k] + d[k][j]);
	
	Nlast = N;
	
	int mn = INF;
	for(i=0;i<N;++i)
	{
		mn = min(mn, a[(1<<N)-1][i]);
		x2[i] = x[i];
		y2[i] = y[i];
		Vl[i] = a[(1<<N)-1][i];
	}
	
	return mn;
}

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

		cin >> cod;
		
		if(cod == 2) continue;
		
		while(cod != 1) 
		{
			cin >> x[N] >> y[N] >> cod;
			++N;
		}

		int ans = solve();
				
		cout << ans << '\n';
			
	}while(cod != 2);
	
	return 0;
}