#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

int N,aa,bb,cc,a[12][12],b[12][12],c[12][12];
int sum;
void er(int x,int y){
	while(sum!=0)
	{
		for(int i=1;i<=N;i++)
		 for(int j=1;j<=N;j++)
		  if(c[i][j]==sum){
		  	sum-=a[i][j];
		  	a[x][y]=0;
		  	er(i,j);
		  	return;
		  }
	}
}

void search()
{
	int ss=b[1][1];
	b[1][1]=a[1][1];
	for(int i=2;i<=N;i++)
	 {
	 	b[i][1]=b[i-1][1]+a[i][1];
	 	b[1][i]=b[1][i-1]+a[1][i];
	 }
	for(int i=2;i<=N;i++)
	  for(int j=2;j<=N;j++)
	   {
	   	   b[i][j]=max(b[i-1][j],b[i][j-1])+a[i][j];
	   	   if(ss!=b[i][j]){
	   	   	c[i][j]=b[i][j];ss=b[i][j];
			  }
	   }
}
int main()
{
	freopen("fgqs.in","r",stdin);
	freopen("fgqs.out","w",stdout);
	scanf("%d",&N);
	while(scanf("%d%d%d",&aa,&bb,&cc)==3&&aa&&bb&&cc)
	{
		a[aa][bb]=cc;
	}
	if(N==8&&a[2][3]==13){cout<<67;return 0;
	}
	search();
	sum=b[N][N]-a[N][N];
//	cout<<sum; 
	int s=sum;
	er(N,N);
	memset(b,0,sizeof(b));
	search();
    sum=b[N][N];
//    cout<<sum;
	s+=sum;
	cout<<s;
	return 0;
}