#include<iostream>
using namespace std;
int n ;
int z , l , ml;
int g[1005][1005] , f[1005][1005], sum = -1 , sum1 = -1;
int dx[4] = {1 , -1 , 0 , 0};
int dy[4] = {0 , 0 , 1 , -1};
void dfs(int x , int y , int ans){
	if(x == n && y == n){
		sum = max(ans , sum) ;
		return ;
	} else {
		for(int i = 0 ; i < 4 ; i ++){
			int tx = x + dx[i] ;
			int ty = y + dy[i] ;
			if(tx > 0 && tx <= n && ty > 0 && ty <= n){
				if(f[tx][ty] == -1){
					f[tx][ty] = 0 ;
					dfs(tx , ty , ans + g[tx][ty]) ;
					g[tx][ty] = 0 ;
				}
			}
		}
	}
}
void dfs1(int x , int y , int ans){
	if(x == 1 && y == 1){
		sum1 = max(ans , sum1) ;
		return ;
	} else {
		for(int i = 0 ; i < 4 ; i ++){
			int tx = x + dx[i] ;
			int ty = y + dy[i] ;
			if(tx > 0 && tx <= n && ty > 0 && ty <= n){
				if(f[tx][ty] == -1){
					f[tx][ty] = 0 ;
					dfs(tx , ty , ans + g[tx][ty]) ;
					g[tx][ty] = 0 ;
				}
			}
		}
	}
}
int main(){
	cin >> n ;
	memset(f , -1 , sizeof(f)) ;
	for(;;){
		cin >> z >> l >> ml ;
		if(z == 0 && l == 0 && ml == 0) break ;
		g[z][l] = ml ;
	}
	dfs(1 , 1 , 0) ;
	dfs1(n , n , 0) ;
	cout << sum + sum1 << endl;
}

这是搜索