...

//洛谷P1004.cpp 
#include<iostream>
#include<string.h>
#include<vector>
using namespace std;
struct xyd{
    int x,y,data;
    xyd(){}
};
int main()
{
	int n;
	cin>>n;
	int map[n+1][n+1];
	int one,two,three;
	for(int i=0;i<=n;i++){
		for(int j=0;j<=n;j++){
			map[i][j]=0;
		}
	}
	while(true){
		cin>>one>>two>>three;
		if(one==0&&two==0&&three==0)break;
		map[one+1][two+1]=three;
	}
	//dijkstra
	vector<xyd> queries;
	xyd tmp=xyd();
	tmp.x=1;tmp.y=1;tmp.data=0;
	queries.push_back(tmp);
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=n;j++){
	        if(map[i][j]){
    	        tmp.x=i;tmp.y=j;tmp.data=map[i][j];
    	        queries.push_back(tmp);
	        }
	    }
	}
	tmp.x=n;tmp.y=n;tmp.data=0;
	queries.push_back(tmp);
	int qulen=queries.size();
	vector<vector<int>> matriks(qulen,vector<int>(qulen,-1));
	for(int i=0;i<qulen;i++){
	    for(int j=i+1;j<qulen;j++){
	        if(queries[j].x>=queries[i].x){
	            matriks[i][j]=queries[j].data;
	        }
	    }
	}
	vector<int> book(qulen,-1);
	vector<int> dist(qulen,-1);
	vector<bool> y(qulen,true);
	dist[0]=0;
	int ynum=qulen-1;
	int step=0,ma=0;
	int dijresult;
	while(ynum){
	    for(int i=0;i<qulen;i++){
	        if(y[i]){
	            ma=i;
	            break;
	        }
	    }
	    for(int i=ma;i<qulen;i++){
	        if(y[i]&&matriks[step][i]>matriks[step][ma])ma=i;
	    }
	    y[ma]=false;ynum--;step=ma;
	    for(int i=0;i<qulen;i++){
	        if(y[i]&&matriks[step][i]+dist[step]>dist[i]){
	            dist[i]=matriks[step][i]+dist[step];
	            book[i]=step;
	        }
	    }
	}
	dijresult=dist[qulen-1];
	step=qulen-1;
	while(step!=0){
	    map[queries[step].x][queries[step].y]=0;
	    step=book[step];
	}
	//dp
	for(int i=1;i<=n;i++){
	    for(int j=1;j<=n;j++){
	        map[i][j]+=max(map[i-1][j],map[i][j-1]);
	    }
	} 
	cout<<dijresult+map[n][n];
	return 0;
}