#include<bits/stdc++.h>
using namespace std;
int n,t[100][100];
int ans1;
pair <int,string> ans;
void dfs(int x,int y,int sum,string way)
{
	if(x>n||y>n) return;
	if(x==n&&y==n)
	{
		if(ans.first>sum) return;
		ans.first=sum;
		ans.second=way;
		return;
	}
	dfs(x+1,y,sum+t[x][y],way+'0');
	dfs(x,y+1,sum+t[x][y],way+'1');
}
void dfs1(int x,int y,int sum)
{
	if(x>n||y>n) return;
	if(x==n&&y==n)
	{
		ans1=max(ans1,sum);
		return;
	}
	dfs1(x+1,y,sum+t[x][y]);
	dfs1(x,y+1,sum+t[x][y]);
}
int main()
{
	scanf("%d",&n);
	int a,b,c;
	do
	{
		scanf("%d%d%d",&a,&b,&c);
		t[a][b]=c;
	}
	while(a||b||c);
	dfs(1,1,0,"");
	t[0][0]=0;
	for(int i=1,j=1,s=0; i<=n&&j<=n;)
	{
		if(ans.second[s++]-'0')
			j++;
		else
			i++;
		t[i][j]=0;
	}
	dfs1(1,1,0);
	printf("%d\n",ans.first+ans1);
	return 0;
}