#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include"debug.h"
#else
#define debug(...) void()
#endif
#define all(x) (x).begin(),(x).end()
template<class T>
auto ary(T *a,int l,int r){
	return vector<T>{a+l,a+1+r};
}
using ll=long long;
using ull=unsigned long long;
const int N=2e2+10,M=N*2;
int n,a[N][N];
vector<int>to[M];
void add(int u,int v){
	to[u].push_back(v);
}
int dft,sct,dfn[M],low[M],scc[M];
void tarjan(int u){
	static int top,stk[M];
	dfn[u]=low[u]=++dft,stk[++top]=u;
	for(int v:to[u]){
		if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
		else if(!scc[v])low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		sct++;
		do scc[stk[top]]=sct;while(stk[top--]^u);
	}
}
bool chk(){
	for(int i=1;i<=n+n;i++)if(!dfn[i])tarjan(i);
	bool flag=1;
	for(int i=1;i<=n;i++)flag&=scc[i]!=scc[i+n];
	for(int i=1;i<=n+n;i++)to[i].clear(),dfn[i]=scc[i]=0;
	return dft=sct=0,flag;
}
int fa[M];
int find(int x){
	return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
	scanf("%d",&n);
	if(n==1)puts("0"),exit(0);
	vector<tuple<int,int,int>>E;
	for(int i=1,x;i<=n;i++){
		E.push_back({0,i,i});
		for(int j=i+1;j<=n;j++){
			scanf("%d",&x);
			a[i][j]=a[j][i]=x;
			E.push_back({x,i,j});
		}
	}
	sort(all(E));
	iota(fa,fa+1+n+n,0);
	bool flag=1;
	int ans=INT_MAX;
	// debug(E);
	for(int i=E.size()-1;i>=0;i--){
		auto [w,u,v]=E[i];
		if(1){
			int l=-1,r=i,mid;
			for(;l+1<r;){
				mid=(l+r)>>1;
				for(int x=E.size()-1;x>i;x--){
					auto [w,u,v]=E[x];
					add(u,v+n),add(v+n,u);
					add(u+n,v),add(v,u+n);
				}
				for(int x=i;x>mid;x--){
					auto [w,u,v]=E[x];
					add(u+n,v),add(v+n,u);
				}
				if(chk())r=mid;
				else l=mid;
			}
			// debug(w,get<0>(E[r]),i,r);
			ans=min(ans,get<0>(E[r])+w);
		}
		if(find(u)==find(v))break;
		if(find(u)==find(v+n))flag=0;
		else flag=1,fa[find(u)]=find(v+n),fa[find(u+n)]=find(v);
	}
	cout<<ans<<endl;
	return 0;
}
#ifdef DEBUG
#include"debug.hpp"
#endif