#include <bits/stdc++.h>
using namespace std;
int n;
int a[20][20];
int f[20][20];
bool v[20][20];
int sum = 0;
inline bool calc (int i, int j) {
	if (i >= 1 && i <= n && j >= 1 && j <= n)
		return true;
	return false;
}
inline void clean () {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (v[i][j] == true)
				a[i][j] = 0;
}
inline void bfs (int x, int y) {
	memset (f, 0, sizeof (f));
	queue <pair <int, int>> p;
	p.push({x, y});
	f[x][y] = a[x][y];
	while (!p.empty()) {
		pair <int, int> x = p.front();
		p.pop();
		int xx, yy;
		xx = x.first;
		yy = x.second;
		xx++;
		if (calc (xx, yy)) {
			f[xx][yy] = max (f[xx][yy], f[xx - 1][yy] + a[xx][yy]);
			p.push({xx, yy});
		}
		xx--;
		yy++; 
		if (calc (xx, yy)) {
			f[xx][yy] = max (f[xx][yy], f[xx][yy - 1] + a[xx][yy]);
			p.push({xx, yy});
		}
	}
}
inline void dfs (int x, int y, int z) {
	if (x == n && y == n) {
		if (z == sum)
			clean();
		return;
	}
	if (calc (x + 1, y) && v[x + 1][y] == false) {
		v[x + 1][y] = true;
		dfs (x + 1, y, z + a[x + 1][y]);
		v[x + 1][y] = false;
	}
	if (calc (x, y + 1) && v[x][y + 1] == false) {
		v[x][y + 1] = true;
		dfs (x, y + 1, z + a[x][y + 1]);
		v[x][y + 1] = false;
	}
}
int main() {
	memset (a, 0, sizeof (a));
	cin >> n;
	while (true) {
		int x, y, z;
		cin >> x >> y >> z;
		if (x == 0 && y == 0 && z == 0)
			break;
		a[x][y] = z;
	}
	bfs (1, 1);
	sum += f[n][n];
	memset (v, false, sizeof (v));
	dfs (1, 1, 0);
	bfs (1, 1);
	sum += f[n][n];
	cout << sum << endl;
	return 0;
}

样例对了