#include<bits/stdc++.h>
#define int long long

using namespace std;
const int N=11;
int a[N][N];
int f[N][N];
vector<pair<int,int>> k[N][N];
int sum=0;

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);cout.tie(0);
  int n;
  cin>>n; 
  while(true) {
  	int u,v,w;
  	cin>>u>>v>>w;
  	if(u+v+w==0) break;
  	a[u][v]=w;
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			if(f[i-1][j]>f[i][j-1]) {
				f[i][j]=f[i-1][j]+a[i][j];
				k[i][j]=k[i-1][j];
				k[i][j].push_back({i,j});
			}
			else {
				f[i][j]=f[i][j-1]+a[i][j];
				k[i][j]=k[i][j-1];
				k[i][j].push_back({i,j});
			}
		}
	}
	for(int i=0;i<k[n][n].size();++i) {
		a[k[n][n][i].first][k[n][n][i].second]=0;
	}
	sum=f[n][n];
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			if(f[i-1][j]>f[i][j-1])
				f[i][j]=f[i-1][j]+a[i][j];
			else
				f[i][j]=f[i][j-1]+a[i][j];
		}
	}
	sum+=f[n][n];
	printf("%lld",sum);
  return 0;
}