#include<stdio.h>
#include<algorithm>
using namespace std;
const int maxn=20;
int n,mp[maxn][maxn],dp[maxn*2][maxn][maxn];

int main()
{
	scanf("%d",&n);
	int a=0,b=0,c=0;
	scanf("%d%d%d",&a,&b,&c);
	while(a||b||c)
	{
		mp[a][b]=c;
		scanf("%d%d%d",&a,&b,&c);
	}
	for(int k=1;k<=2*n;k++)
	{
		for(int i1=1;i1<=n;i1++)
		{
			for(int i2=1;i2<=n;i2++)
			{
				int j1=k-i1;
				int j2=k-i2;
				int t=mp[i1][j1];
				if(i1!=i2)
					t+=mp[i2][j2];
				dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1-1][i2-1]+t);
				dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1][i2-1]+t);
				dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1-1][i2]+t);
				dp[k][i1][i2]=max(dp[k][i1][i2],dp[k-1][i1][i2]+t);
			}
		}
	}
	printf("%d",dp[2*n][n][n]);
	return 0;
}

PS:4号数据点：

in：

8
1 1 13
1 3 7
1 8 14
2 2 1
2 4 2
4 3 5
5 5 4
6 2 6
7 8 16
0 0 0

out:

60

maxn=15时，out

66