代码如下：

// I love CCF!
#include <bits/stdc++.h>
using namespace std;

struct From
{
    int xx;
    int yy;
} f[15][15];    // 记录每个格子的上承格子的坐标

int main()
{
    int n = 0; cin >> n;
    int a[15][15] = {};
    int x = 0, y = 0, k = 0;
    cin >> x >> y >> k;
    while (x || y || k)
    {
        a[x][y] = k;
        cin >> x >> y >> k;
    }
    int ans = 0;
    int dp[15][15] = {};
    int i = 0, j = 0;
    // 进行第一条路径的dp
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
            if (dp[i - 1][j] > dp[i][j - 1])
            {
                f[i][j].xx = i - 1;
                f[i][j].yy = j;
            }
            else
            {
                f[i][j].xx = i;
                f[i][j].yy = j - 1;
            }
        }
    ans += dp[n][n];
    memset(dp, 0, sizeof(dp));

    // 从最后一个格子开始往前回溯，路线上的格子均修改为0，直到回到起点
    int tmpi = 0, tmpj = 0;
    i--, j--;
    a[i][j] = 0;
    while (i != 0 || j != 0)
    {
        tmpi = f[i][j].xx; tmpj = f[i][j].yy;
        a[tmpi][tmpj] = 0;
        i = tmpi; j = tmpj;
    }

    // 进行第二条路径的dp
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
        }
    ans += dp[n][n];
    cout << ans << endl;
    return 0;
}