//P1004 [NOIP2000 提高组] 方格取数 
#include<iostream>
#include<iomanip>
using namespace std;
int fg[9][9], N, mx[3];
char fx[17], fxl[17];
void yd(int x, int y, int t, int ii, int cs)
{
	int tt=t+fg[x][y];
	if(x==N&&y==N)
	{
		if(tt > mx[cs])
		{
			for(int i=1;i<ii;i++)fx[i]=fxl[i];
			mx[cs]=tt;
		}
	}
	if(x+1 <= N)
	{
		fxl[ii]='x';
		yd(x+1,y,tt,ii+1,cs);
	}
	if(y+1 <= N)
	{
		fxl[ii]='y';
		yd(x,y+1,tt,ii+1,cs);
	}
}
int main()
{
	cin >> N;
	for( ; ; )
	{
		int a, b, c;
		cin >> a >> b >> c;
		if(a==0&&b==0&&c==0)break;
		fg[a][b]=c;
	}
	yd(0, 0, 0, 1, 1);
	for(int i=1,x=0,y=0; i<=16; i++)
	{
		fg[x][y]=0;
		if(fx[i]=='x')x++;
		if(fx[i]=='y')y++;
	}
	yd(0, 0, 0, 1, 2);
	cout << mx[1]+mx[2];
	return 0;
}