#include <stdio.h>

const int n_max = 30;

int x[2][n_max],
    y[2][n_max],
    cost[n_max];
int d[1<<17][20];
int cur, pre, i, j, on ,n,c;

inline int min(int x, int y)
{
	if (x < y)
		return x;
	return y;
}

inline int dist(int a, int b)
{
	int xx = x[cur][a] - x[cur][b];
	int yy = y[cur][a] - y[cur][b];
	int x1 = xx*xx;
	int y1 = yy*yy;
	return x1 + y1;
}

inline int s_dist(int a, int b)
{
	int xx = x[pre][a] - x[cur][b];
	int yy = y[pre][a] - y[cur][b];
	int x1 = xx*xx;
	int y1 = yy*yy;
	return x1 + y1;
}

void back(int key, int t)
{
	for (int i = 1; i <= n; ++ i)
		if ( (key & (1<<(i-1)))== 0)
		{
			int x = key | (1<<(i-1));
			if (d[x][i] == -1)
			{
				d[x][i] = d[key][t] + dist(t,i);
				back(x,i);
			}
			else
			if (d[x][i] > d[key][t] + dist(t, i))
			{
				d[x][i] = d[key][t] + dist(t,i);
				back(x, i);
			}
		}

}
			
void solve()
{
	int i, j;
	//Generarea starilor initiale. E buna si ramane!
	for (i = 1; i < 1<<n; ++ i)
		for (j = 1; j <= n; ++ j)
			d[i][j] = -1;
	for (i = 1; i <= n; ++ i)
		for (j = 1; j <= on; ++ j)
		{
			if (d[1<<(i-1)][i] == -1 || d[1<<(i-1)][i] > s_dist(j,i)+cost[j])
				d[1<<(i-1)][i] = s_dist(j,i)+cost[j];
		}
	// End of generare
	
	for (i = 1; i <= n; ++ i)
		back(1<<(i-1), i);
	
	//Gasirea minimului. E buna si ramane!
	int minim = 1<<30;
	for (i = 1; i <= n; ++ i)
	{
		cost[i] = d[(1<<n)-1][i];
		minim = min(minim, d[(1<<n)-1][i]);
	}
	printf("%d\n",minim);

}
int main()
{
	freopen("bibel.in","r", stdin);
	freopen("bibel.out","w", stdout);
	scanf("%d", &c);
	x[1][1] = 0;
	y[1][1] = 0;
	on = 1;
	cur = 0;
	pre = 1;
	while (c == 0)
	{
		
		i = 0;
		while (c == 0)
		{
			++i;
			scanf("%d %d %d", &x[cur][i], &y[cur][i], &c);
		}
		n = i;
		solve();
		pre = cur;
		cur = 1 - cur;
		on = n;
		scanf("%d", &c);
	}
	return 0;
}