/*这个题我想的是分三步：
第一步先是求出他的第一次走完全部路程找到那个最大值，这个我在程序里已经实现了能求出正确的解，使用了动态规划的算法思维。
第二步我是想自己写一种数据结构就是下面的road类型，里面存放着两个数组，x与y按顺序组合成（x,y）代表着到达现在位置的路径
现在我就是卡在了第二步。
第三步就是将第一次跑完的路径上的数字清零，最后再按照第一部的过程跑一遍就行了
但是第二步的数组我一直没维护好，现在问题是数组下标越界，还有数组结果和预期不一样
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 9
typedef struct{
 int x[2*N-1];
 int y[2*N-1];
}road;
void scpy(int*,const int*);
int funtion(int n);
int max(int ,int );
int main()
{
    int n,score;
    scanf("%d",&n);
    score = funtion(n);
    printf("%d",score);
    return 0;
}
int funtion(int n)//实现主要功能
{
    road r[n][n];//建立一个二维的存储结构
    int i,j,k;
//    for(i=0;i<N;i++)
//    {
//        for(j=0;j<N;j++)
//        {
//            for(k=0;k<2*N-1;k++)
//            {
//                r[i][j].x[k]=0;
//                r[i][j].y[k]=0;
//            }
//        }
//    }
    int a[n][n];
    int x,y,z;
    int judge;
    judge=0;
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            a[i][j]=0;
        }
    }//先初始化地图数组
    do
    {
        scanf("%d%d%d",&x,&y,&z);
    if(x==0&&y==0&&z==0);
    else
        a[x][y]=z;
    if(x==0&&y==0&&z==0)
        judge=1;
    }while(judge==0);//按题目要求初始化初值
//    for(i=0;i<N;i++)
//    {
//        for(j=0;j<N;j++)
//        {
//            for(k=0;k<2*N-1;k++)
//            {
//                r[i][j].x[k]=0;
//                r[i][j].y[k]=0;
//            }
//        }
//    }
    int f[n][n];
    int sum1=0;
    int sum2=0;
    for(i=0;i<n;i++)
    {
        sum1+=a[i][0];
        f[i][0]=sum1;//初始化dp数组边界初值便于之后递推
        if(i!=0)
        {
            scpy(r[i][0].x,r[i-1][0].x);
            scpy(r[i][0].y,r[i-1][0].y);
            scpy(r[0][i].x,r[0][i-1].x);
            scpy(r[0][i].y,r[0][i-1].y);
            r[i][0].x[i]=i;
            r[i][0].y[i]=0;
            r[0][i].x[i]=0;
            r[0][i].y[i]=i;
        }
        else{
        r[0][0].x[0]=0;
        r[0][0].y[0]=0;
        }
        sum2+=a[0][i];
        f[0][i]=sum2;
    }
    for(i=1;i<n;i++)
    {
        for(j=1;j<n;j++)
        {
            f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];//转移方程
            if((f[i][j]-a[i][j])==f[i-1][j])
            {
                scpy(r[i][j].x,r[i-1][j].x);
                scpy(r[i][j].y,r[i-1][j].y);
                r[i][j].x[i+j]=i;
                r[i][j].y[i+j]=j;
            }
        }
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            printf("%2d",a[i][j]);
        }
        printf("\n");
    }//这个方便我看程序有没有问题
    for(i=0;i<2*n-1;i++)
    {
        printf("(%d,%d)\n",r[n-1][n-1].x[i],r[n-1][n-1].y[i]);
    }
    return f[n-1][n-1];
}
int max(int a,int b)
{
    if(a>b)
        return a;
    else
        return b;
        return b;
}
void scpy(int*a,const int*b)
{
    int i;
    for(i=0;i<2*N-1;i++)
    {
        a[i]=b[i];
    }
    return ;
}