#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <map> 
#include <string>
#include <vector>  
#include <iostream> 
#include <sstream> 
#include <queue>
#include <algorithm>

using namespace std;
 
#define ll long long
#define PB 		push_back
#define FOR(a,start,end) 	for(ll a=ll(start); a<ll(end); a++)
#define INF 		INT_MAX
#define SORT(a) 	sort(a.begin(),a.end()) 
#define CL(a,x) 		memset(a,x,sizeof(a))
#define REP(a,x)	for(ll a=0;a<x;a++)
#define REP1(a,x)	for(ll a=1;a<=x;a++)
#define MP 		make_pair

 
 
typedef vector<int>     vi;
typedef pair<int,int>     pii; 
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vector<int> > vvi;
typedef vector<vector<string> > vvs;
typedef vector<pair<string,string> > vss;
typedef pair<string,string> pss; 
typedef pair<int,pii> ppii;
typedef vector<ppii> vppii;
typedef vector<vector<pii> > vvii;
typedef vector<vvi> vvvi;


ppii px;
vppii vc;
int i0,i,j,k,n,a,a2,k1,k2,k3,k4;
ll z,c,d,t;
ll m,b; 
ll cas,g,ng,p,np;
ll w1,w2,h1,h2;
ll wmin,wmax,hmin,hmax;
vi vk;

vvi vvk,vvp;	
pii p1,p2,p0; 
ll ta[2010][2010];

 
int main() {  
	//freopen( "c:\\wojtek\\uva\\pa\\debug\\kug16.in", "rt", stdin);  
	//	ll czas=clock(); 
	//pi=2*acos(0.0);
	 
	//scanf("%ld",&t); 

	cin>>n;
	CL(ta,0); 
		
	for(i=0;i<n;i++){
		for(j=0;j<n-i;j++){
			cin>>a;
			vc.push_back(MP(a,MP(i,j+i)));
		}
	}
	SORT(vc);
	vk.clear();
	vvk.assign(n,vk);
	vvp.assign(n,vk);
	k=0;
	i0=0;
	while(k<n){
		px=vc[i0];
					//spr
		if(ta[px.second.first][px.second.second]==0){
			b=0;
			
			a=px.second.first;
						//różnice
			for(j=0;j<vvk[px.second.second].size();j++){
				a2=vvk[px.second.second][j];
				if(ta[min(a,a2)][max(a,a2)-1]!=0){
					b=1;
					break;
				}
			}
			if(b==0){
				a=px.second.second;
							//różnice
				for(j=0;j<vvp[px.second.first].size();j++){
					a2=vvp[px.second.first][j];
					if(ta[min(a,a2)+1][max(a,a2)]!=0){
						b=1;
						break;
					}
				}
			}

			/*
			if(b==0){
				
					for(i=0;i<vvp[px.second.first].size();i++){
						a=vvp[px.second.first][i];
						if(ta[min(a,px.second.second)][max(a,px.second.second)]==0){
							//if(px.second.second<n-1){
								for(j=0;j<vvk[px.second.second].size();j++){
									a2=vvk[px.second.second][j];
									if(ta[min(a,a2)][max(a,a2)]!=0){
										b=1;
										break;
									}
								}
							//}

						}
						else
							b=1;
					}
				
			}
			*/
			//dodane
			if(b==0){
				
					for(i=0;i<vvp[px.second.first].size();i++){
						a=vvp[px.second.first][i];
						if(ta[min(a,px.second.second)+1][max(a,px.second.second)]==0){
							if(px.second.second<n-1){
								for(j=0;j<vvp[px.second.second+1].size();j++){
									a2=vvp[px.second.second+1][j];
									if(ta[min(a,a2)+1][max(a,a2)]!=0){
										b=1;
										break;
									}
								}
							}

						}
						else
							b=1;
					}
				
			}
			//dodane
			if(b==0){
				
				for(i=0;i<vvk[px.second.second].size();i++){
					a=vvk[px.second.second][i];
					if(ta[min(a,px.second.first)][max(a,px.second.first)-1]==0){
						if(px.second.first>0){
							for(j=0;j<vvk[px.second.first-1].size();j++){
								a2=vvk[px.second.first-1][j];
								if(ta[min(a,a2)][max(a,a2)-1]!=0){
									b=1;
									break;
								}
							}
						}

					}
					else
						b=1;
				}
			
			}
			
			if(b==0){
				a=px.second.first;

				if(px.second.second<n-1){
					for(j=0;j<vvp[px.second.second+1].size();j++){
						a2=vvp[px.second.second+1][j];
						if(ta[a][a2]!=0){
							b=1;
							break;
						}
					}
				}
			}
			if(b==0){
				a2=px.second.second;

				if(px.second.first>0){
					for(j=0;j<vvk[px.second.first-1].size();j++){
						a=vvk[px.second.first-1][j];
						if(ta[a][a2]!=0){
							b=1;
							break;
						}
					}
				}
			}
			if(b==0){
				if(px.second.first>0){
					for(i=0;i<vvk[px.second.first-1].size();i++){
						a=vvk[px.second.first-1][i];
						if(ta[a][px.second.second]==0){
							if(px.second.second<n-1){
								for(j=0;j<vvp[px.second.second+1].size();j++){
									a2=vvp[px.second.second+1][j];
									if(ta[a][a2]!=0){
										b=1;
										break;
									}
								}
							}

						}
						else
							b=1;
					}
				}
			}
			if(b==0){		//ok
							//dodaj
				
				//dodatek
				//dodatek
				if(px.second.first>0)
					k1=vvk[px.second.first-1].size();
				else
					k1=0;
				if(px.second.second<n-1)
					k2=vvp[px.second.second+1].size();
				else
					k2=0;
				k3=vvk[px.second.second].size();
				k4=vvp[px.second.first].size();
				a=px.second.first;
						//różnice
				for(j=0;j<k3;j++){
					a2=vvk[px.second.second][j];
					if(a>0||a2>0){
						ta[min(min(a,a2),max(a,a2)-1)][max(min(a,a2),max(a,a2)-1)]=1;
						vvp[min(min(a,a2),max(a,a2)-1)].push_back(max(min(a,a2),max(a,a2)-1));
						vvk[max(min(a,a2),max(a,a2)-1)].push_back(min(min(a,a2),max(a,a2)-1));
					}
				}
				
					a=px.second.second;
								//różnice
					for(j=0;j<k4;j++){
						a2=vvp[px.second.first][j]; 
						if(a<n-1||a2<n-1){
							ta[min(max(a,a2),min(a,a2)+1)][max(min(a,a2)+1,max(a,a2))]=1;
							vvp[min(max(a,a2),min(a,a2)+1)].push_back(max(min(a,a2)+1,max(a,a2)));
							vvk[max(min(a,a2)+1,max(a,a2))].push_back(min(max(a,a2),min(a,a2)+1));
						}
					}

				a=px.second.first;
				if(px.second.second<n-1){
					for(j=0;j<k2;j++){
						a2=vvp[px.second.second+1][j];
						ta[a][a2]=1;
						vvp[a].push_back(a2);
						vvk[a2].push_back(a);
						
					}
				}
				if(px.second.first>0){
					
					for(i=0;i<k1;i++){
						a=vvk[px.second.first-1][i];
						ta[a][px.second.second]=1;
						vvp[a].push_back(px.second.second);
						vvk[px.second.second].push_back(a);
						if(px.second.second<n-1){
							
							for(j=0;j<k2;j++){
								a2=vvp[px.second.second+1][j];
								ta[a][a2]=1;
								vvp[a].push_back(a2);
								vvk[a2].push_back(a);
						
							}
						}
					}
				
				}
				//dodane
				/*
				for(i=0;i<k4;i++){
						a=vvp[px.second.first][i];
						
								for(j=0;j<k3;j++){
									a2=vvk[px.second.second][j];
									//if(a<n-1||a2<n-1){
										ta[min(a,a2)][max(a,a2)]=1;
										vvp[min(a,a2)].push_back(max(a,a2));
										vvk[max(a,a2)].push_back(min(a,a2));
									//}
								}
						
				}
				*/
				
				for(i=0;i<k4;i++){
						a=vvp[px.second.first][i];
						
							if(px.second.second<n-1){
								for(j=0;j<k2;j++){
									a2=vvp[px.second.second+1][j];
									if(a<n-1||a2<n-1){
										ta[min(max(a,a2),min(a,a2)+1)][max(min(a,a2)+1,max(a,a2))]=1;
										vvp[min(max(a,a2),min(a,a2)+1)].push_back(max(min(a,a2)+1,max(a,a2)));
										vvk[max(min(a,a2)+1,max(a,a2))].push_back(min(max(a,a2),min(a,a2)+1));
									}
								}
							}

						
				}
				
				
				for(i=0;i<k3;i++){
					a=vvk[px.second.second][i];
					
						if(px.second.first>0){
							for(j=0;j<k1;j++){
								a2=vvk[px.second.first-1][j];
								if(a>0||a2>0){
										ta[min(min(a,a2),max(a,a2)-1)][max(min(a,a2),max(a,a2)-1)]=1;
										vvp[min(min(a,a2),max(a,a2)-1)].push_back(max(min(a,a2),max(a,a2)-1));
										vvk[max(min(a,a2),max(a,a2)-1)].push_back(min(min(a,a2),max(a,a2)-1));
								}
							}
						}

				}
				
				/*
				if(px.second.first>0){
					for(i=0;i<k1;i++){
						a=vvk[px.second.first-1][i];
						
							if(px.second.second<n-1){
								for(j=0;j<k2;j++){
									a2=vvp[px.second.second+1][j];
									//if(a<n-1||a2<n-1){
										ta[min(a,a2)][max(a,a2)]=1;
										vvp[min(a,a2)].push_back(max(a,a2));
										vvk[max(a,a2)].push_back(min(a,a2));
									//}
								}
							}

					}
				}
				*/
				k++;
				z+=(ll)px.first;
			
				ta[px.second.first][px.second.second]=1;
				vvp[px.second.first].push_back(px.second.second);
				vvk[px.second.second].push_back(px.second.first);
			
			}
		}
		i0++;
	}

	cout<<z<<endl;
	

	//czas = clock() - czas;
	//printf("%lf\n",double(czas)/CLOCKS_PER_SEC);					

			
	return 0;
	 
}