WA #3 #5 #6 #7

#include <bits/stdc++.h>
using namespace std;

int n;
int a[15][15];
int dp[15][15];
int dp2[15][15];
int ans1,ans2,ans;

int main(){
   cin >> n;
   
   int x,y,c;
   while(cin >> x >> y >> c){
   	if (x == 0) break;
   	a[x][y] = c;
   	dp[x][y] = c;
   	dp2[x][y] = c;
   }
   
   // dp round 1
   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]);
//			if (dp[i-1][j] >= dp[i][j-1]) dp2[i-1][j] = 0;
//			else dp2[i][j-1] = 0;
   	}
   }
   
//	cout << dp[n][n] << endl;
   ans1 = dp[n][n];
   ans2 = ans1; 
   
   // 删除轨迹 
   for (int i =n; i>= 1;i--){
   	for (int j = n; j >= 1; j--){
//			dp2[i][j] += max(dp2[i-1][j],dp2[i][j-1]);
   		if (ans1 - dp2[i][j] == dp[i-1][j]){
   			ans1 -= dp2[i][j];
   			dp2[i][j] = 0;
   		} if(ans1 - dp2[i][j] == dp[i][j-1]){
   			ans1 -= dp2[i][j];
   			dp2[i][j] = 0;
   		}
   	}
   }
   
//	for (int i =1; i<= n;i++){
//		for (int j = 1; j <= n; j++){
//			cout << dp2[i][j] << " ";
//		}
//		cout << endl;
//	}
//	
   
   // dp round 2
   for (int i =1; i<= n;i++){
   	for (int j = 1; j <= n; j++){
   		dp2[i][j] += max(dp2[i-1][j],dp2[i][j-1]); 
   	}
   }
   
   ans2 += dp2[n][n];
   
   cout << ans2 << endl;
   
   
   
   return 0;
}