#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
/*
>mx:双向
>mn：单向 
*/
const int mxn=1e5+5;
struct edge
{
	int x,y,v;
	friend bool operator <(const edge &x,const edge &y)
	{
		return x.v<y.v;
	}
}e[mxn];
int f[mxn];
int find(int x)
{
	return f[x]==x?x:f[x]=find(f[x]);
}
int n,m;
vector<int> a[mxn];
int dfn[mxn],low[mxn],col[mxn],dcnt,ccnt;
bool vis[mxn];
stack<int> stk;
void dfs(int d)
{
	stk.push(d),vis[d]=1;
	dfn[d]=low[d]=++dcnt;
	for(auto x:a[d])
		if(!dfn[x])
		{
			dfs(x);
			low[d]=min(low[d],low[x]);
		}
		else if(vis[x])
			low[d]=min(low[d],dfn[x]);
	if(dfn[d]==low[d])
	{
		ccnt++;
		int p;
		do
		{
			p=stk.top();
			stk.pop(),vis[p]=0;
			col[p]=ccnt;
		}while(p!=d);
	}
}
bool check(int l,int r)
{
	int i,j;
	for(i=1;i<=n*2;i++)
		a[i].clear();
	for(i=l+1;i<=r;i++)
		a[find(e[i].x)].push_back(find(e[i].y+n)),
		a[find(e[i].y)].push_back(find(e[i].x+n));
	memset(dfn,0,n*2+1<<2);
	for(i=1;i<=n*2;i++)
		if(!dfn[i])
			dfs(i);
	for(i=1;i<=n;i++)
		if(col[find(i)]==col[find(i+n)])
			return 0;
	return 1;
}
int main()
{
	n=read();
	int i,j,ans;
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
			e[++m].x=i,e[m].y=j,e[m].v=read();
	sort(e+1,e+1+m);
	ans=e[m].v;
	for(i=1;i<=n*2;i++)
		f[i]=i;
	for(i=m;i;i--)
		if(find(e[i].x)!=find(e[i].y+n)||find(e[i].x+n)!=find(e[i].y))
		{
			int w=i;
			for(j=1<<__lg(i);j;j>>=1)
				w-=(w-j>=1&&check(w-j,i))*j;
			if(w<i)
				ans=min(ans,e[i].v+e[w].v);
			f[find(e[i].x)]=find(e[i].y+n);
			f[find(e[i].x+n)]=find(e[i].y);
		}
	cout<<ans;
}