#求助！看了题解自己打的，全TLE了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int f[10][10][10][10]={0},map[10][10]={0};
int n,i=1,j=1,k,l,temp1,temp2;
int main()
{
    scanf("%d",&n);
    while(i!=0||j!=0||f[i][j]!=0)
    {
      scanf("%d %d",&i,&j);
	  scanf("%d",&map[i][j]);
    }
    for(i=1;i<=9;i++)
      for(j=1;j<=9;j++)
        for(k=1;k<=9;k++)
          for(l=1;l<=9;l++)
          {
            temp1=max(f[i-1][j][k-1][l],f[i][j-1][k][l-1]);
            temp2=max(f[i-1][j][k][l-1],f[i][j-1][k-1][l]);
            f[i][j][k][l]+=max(temp1,temp2)+map[i][j];
            if(i!=k&&j!=l)
              f[i][j][k][l]+=map[k][l];
          }
    printf("%d",f[n][n][n][n]);
    return 0;
}