#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff
	int len=0;
	char ibuf[(1<<21)+1],*iS,*iT,out[(1<<25)+1];
	#if ONLINE_JUDGE
	#define gh() (iS==iT?iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT?EOF:*iS++):*iS++)
 	#else
	#define gh() getchar()
	#endif
	#define reg register
	inline int read(){
		reg char ch=gh();
		reg int x=0;
		reg char t=0;
		while(ch<'0'||ch>'9')   t|=ch=='-',ch=gh();
		while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=gh();
		return t?-x:x;
	}
	inline void putc(char ch){
		out[len++]=ch;
	}
	template<class T>
	inline void write(T x){
		if(x<0)putc('-'),x=-x;
		if(x>9)write(x/10);
		out[len++]=x%10+48;
	}
	inline void flush(){
		fwrite(out,1,len,stdout);
		len=0;
	}
	inline char getc(){
		char ch=gh();
		while(ch<'A'||ch>'Z') ch=gh();
		return ch;
	}
}
using IO::read;
using IO::write;
using IO::flush;
using IO::getc;
using IO::putc;
#define pii pair<int,int>
#define mpr make_pair
#define fir first
#define sec second
const int N=400+10,INF=1e9+10;
int n,d[N][N];
struct node{
	int u,v,w;
	inline friend bool operator<(const node &a,const node &b){
		return a.w>b.w;
	}
};
vector<node>vec;
vector<int>a[N],b[N];
int vis[N][2];
inline int bfs(int s,int t){
	for(int i=1;i<=n;i++)
		vis[i][0]=vis[i][1]=0;
	vis[s][0]=1;
	queue<pii>q;
	q.push(mpr(s,0));
	while(!q.empty()){
		int x=q.front().fir,d=q.front().sec;
		q.pop();
		for(auto t:a[x])
			if(!vis[t][!d])
				vis[t][!d]=1,q.push(mpr(t,!d));
	}
	if(vis[t][0]) return -1;
	if(vis[t][1]) return 1;
	return 0;
}
int dfn[N],low[N],stk[N],top,bel[N],tim,inc[N],bc;
inline void Tarjan(int x){
	dfn[x]=low[x]=++tim,stk[++top]=x,inc[x]=1;
	for(auto t:b[x]){
		if(!dfn[t]) Tarjan(t),low[x]=min(low[x],low[t]);
		else if(inc[t]) low[x]=min(low[x],dfn[t]);
	}
	if(dfn[x]==low[x]){
		bc++;
		while(1){
			int p=stk[top--];
			inc[p]=0,bel[p]=bc;
			if(p==x) break;
		}
	}
}
inline void clear(){
	for(int i=1;i<=n*2;i++)
		b[i].clear();
	for(int i=1;i<=n*2;i++)
		dfn[i]=bel[i]=inc[i]=0;
	tim=bc=0;
}
inline bool check(int x){
//	printf("---check(%d)---\n",x);
	for(int i=1;i<=n;i++)
		for(auto j:a[i])
			b[i].push_back(j+n);//,printf("%d %d\n",i,j+n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(d[i][j]>x)
				b[i+n].push_back(j);//,printf("%d %d\n",i+n,j);
	for(int i=1;i<=n*2;i++)
		if(!dfn[i])
			Tarjan(i);
	bool fl=1;
	for(int i=1;i<=n;i++)
		if(bel[i]==bel[i+n])
			fl=0;
//	for(int i=1;i<=n;i++)
//		printf("(%d,%d) ",bel[i],bel[i+n]);puts("");
//	for(int i=1;i<=n;i++)
//		printf(bel[i]>bel[i+n]?"B":"A");
//	puts("");
	clear();
	return fl;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			vec.push_back({i,j,d[i][j]=d[j][i]=read()});
	if(n<=2) return puts("0"),0;
	sort(vec.begin(),vec.end());
//	for(int i=1;i<=n;i++,puts(""))
//		for(int j=1;j<=n;j++)
//			printf("%3d ",d[i][j]);
	int ans=INF*2,fl=0;
	for(auto e:vec){
		int u=e.u,v=e.v;
		int tp=bfs(u,v);
//		printf("(%d,%d) %d\n",u,v,e.w);
		if(tp==-1){ fl=1;break; }
		if(!tp){
			int L=0,R=vec.size()-1,res=-1;
			while(L<=R){
				int mid=L+R>>1;
				if(check(vec[mid].w)) L=mid+1,res=vec[mid].w;
				else R=mid-1;
			}
//			printf("%d %d\n",e.w,res);
			if(res!=-1) ans=min(ans,e.w+res);
		}
		a[u].push_back(v);
		a[v].push_back(u);
	}
	int L=0,R=vec.size()-1,res=-1;
	while(L<=R){
		int mid=L+R>>1;
		if(check(vec[mid].w)) L=mid+1,res=vec[mid].w;
		else R=mid-1;
	}
	if(res!=-1) ans=min(ans,res);
	write(ans);
	flush();
}