#include<cstdio>
#include<cstring>
using namespace std;
int map[10][10];
int dp[10][10];
int d[10][10];
int n;
int a=1,b=1,c=1;
int r1,r2;
void init_1()
{
	memset(dp,0,sizeof(dp));
	memset(d,0,sizeof(d));
	dp[1][1]=map[1][1];
	for(int i=2;i<=n;i++)
	{
		dp[i][1]=map[i][1]+dp[i-1][1];
		d[i][1]=1;
		dp[1][i]=map[1][i]+dp[1][i-1];
		d[1][i]=2;
	}
}
void init_2()
{
	memset(dp,0,sizeof(dp));
	memset(d,0,sizeof(d));
	dp[n][n]=map[n][n];
	for(int i=n-1;i>=1;i--)
	{
		dp[i][n]=map[i][n]+dp[i-1][n];
		d[i][n]=3;
		dp[n][i]=map[n][i]+dp[n][i-1];
		d[n][i]=4;
	}
}
int main()
{
	scanf("%d",&n);
	while(a!=0&&b!=0&&c!=0)
	{
		scanf("%d%d%d",&a,&b,&c);
		map[a][b]=c;
	}
	init_1();
	for(int i=2;i<=n;i++)
		for(int j=2;j<=n;j++)
		{
			if(dp[i-1][j]>=dp[i][j-1])
			{
				d[i][j]=1;
				dp[i][j]=dp[i-1][j]+map[i][j];
			}
			else
			{
				d[i][j]=2;
				dp[i][j]=dp[i][j-1]+map[i][j];
			}
		}
	//	1from up 2 from left
	r1=dp[n][n];
	int x,y;
	x=y=n;
	while(x!=1&&y!=1)
	{
		map[x][y]=0;
		if(d[x][y]==1) x--;
		else y--;
	}
	r1=dp[n][n];
	init_2();
	for(int i=n-1;i>=1;i--)
		for(int j=n-1;j>=1;j--)
		{
			if(dp[i+1][j]>=dp[i][j+1])
			{
				d[i][j]=3;
				dp[i][j]=dp[i+1][j]+map[i][j];
			}
			else
			{
				d[i][j]=4;
				dp[i][j]=dp[i][j+1]+map[i][j];
			}
		}
	r1+=dp[1][1];
	printf("%d",r1); 
	return 0;
}

蒟蒻用两个dp，WA了4个点