#include<iostream>
using namespace std;
int arr[11][11],a,c[2][2]={{0,1},{1,0}},book[101][101],g[101][2],max1,sum=0,ans=0,t=0,sum1;
void dfs(int x,int y,int c1){//这里是深搜
	if(x==a&&y==a){//判断终点
		ans=max(ans,sum);//最大值
		if(ans==max1){//这里的作用是把最大值一样的路径上所有点变为0
			for(int i=1;i<=c1;i++){
				arr[g[i][0]][g[i][1]]=0;
			}
			arr[0][0]=0;//同理起点
		}
		
		return;
	}
	for(int i=0;i<=1;i++){
		for(int d=0;d<=1;d++){
			int xx=x+c[0][i];
			int yy=y+c[1][d];
			if(xx<=a&&yy<=a&&book[xx][yy]==0){
				book[xx][yy]=1;
				g[c1][0]=xx;//记录走的x
				g[c1][1]=yy;//记录走的y
				sum+=arr[xx][yy];
				dfs(xx,yy,c1+1);
				book[xx][yy]=0;
				sum-=arr[xx][yy];
			}
		}
	}
}
int dps(){//新的brr用动规来求最大值
	int brr[11][11]={};
	for(int i=1;i<=a;i++){
		for(int d=1;d<=a;d++){
			brr[i][d]=arr[i][d];
		}
	}
	brr[0][0]=0;
	for(int i=1;i<=a;i++){
		for(int d=1;d<=a;d++){
			brr[i][d]=max(brr[i-1][d],brr[i][d-1])+brr[i][d];
		}
	}
	return brr[a][a];
}
int main(){
	int x,y,z;
	cin >> a;
	while(cin >> x >> y >> z){
		if(!x&&!y&&!z)break;
		arr[x][y]=z;
	}
	max1 = dps();//最大值
	book[1][1]=1;//起点标了
	dfs(1,1,1);//开始深搜
	for(int i=1;i<=a;i++){//arr数组的动规（删去了最大路径上的数之后执行
		for(int d=1;d<=a;d++){
			arr[i][d]=max(arr[i-1][d],arr[i][d-1])+arr[i][d];
		}
	}
//	for(int i=1;i<=a;i++){
//		for(int d=1;d<=a;d++){
//			cout << arr[i][d] << " ";
//		}
//		cout << endl;
//	}这个是测试
	cout << arr[a][a] + max1;//输出
	return 0;
}

帮帮蒟蒻，写了好久没过:>