//qoj7671
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 410;
int n, e[N][N], tot, ans = 2e9 + 10, fa[N], siz[N], col[N];
vector<int> son[N];
struct edge{
	int val, x, y;
} eg[N*N];

bool cmp(edge x, edge y){
	return x.val > y.val;
}
int gf(int x){
	return fa[x] == x ? x : gf(fa[x]);
}
void dfs(int x, int cl){
	col[x] = cl;
	for(int i : son[x]){
		dfs(i, 1-cl);
	}
}
void mg(int x, int y){
	if(siz[x] > siz[y]) swap(x, y);
	son[y].push_back(x);
	siz[y] += siz[x];
	dfs(x, 1 - col[y]);
}

int dfn[N], low[N], scc[N], sct, cnt, ins[N], st[N], tp;
vector<int> g[N];
void add(int x, int y){
	g[x].push_back(y);
}
void tg(int x){
	dfn[x] = low[x] = ++ cnt;
	ins[x] = 1;
	st[++tp] = x;
	for(int i : g[x]){
		if(!dfn[i]){
			tg(i);
			low[x] = min(low[x], low[i]);
		} else if(ins[i]){
			low[x] = min(low[x], dfn[i]);
		}
	}
	if(dfn[x] == low[x]){
		++ sct;
		while(st[tp] != x){
			scc[st[tp]] = sct;
			ins[st[tp]] = 0;
			-- tp;
		}
		scc[st[tp]] = sct;
		ins[st[tp]] = 0;
		-- tp;
	}
}

bool chk(int p, int q){
	sct = cnt = tp = 0;
	for(int i = 1; i <= n + n; ++ i){
		vector<int> ().swap(g[i]);
		dfn[i] = low[i] = scc[i] = ins[i] = st[i] = 0;
	}
	for(int i = 1; i <= tot; ++ i){
		int x = eg[i].x, y = eg[i].y;
		if(i == p){
			add(x + n, x);
			add(y + n, y);
		} else if(i < p){
			add(x, y + n);
			add(x + n, y);
			add(y, x + n);
			add(y + n, x);
		} else if(eg[i].val > q){
			add(x + n, y);
			add(y + n, x);
		}
	}
	for(int i = 1; i <= n + n; ++ i){
		if(!dfn[i]){
			tg(i);
		}
	}
	for(int i = 1; i <= n; ++ i){
		if(scc[i] == scc[i+n]){
			return 0;
		}
	}
	return 1;
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i){
		fa[i] = i;
		siz[i] = 1;
		col[i] = 0;
		for(int j = i + 1; j <= n; ++ j){
			scanf("%d", &e[i][j]);
			e[j][i] = e[i][j];
			eg[++tot] = (edge){ e[i][j], i, j };
		}
	}
	sort(eg + 1, eg + tot + 1, cmp);
	for(int i = 1; i <= tot; ++ i){
		int flg = 0;
		if(gf(eg[i].x) == gf(eg[i].y)){
			if(col[eg[i].x] == col[eg[i].y]){
				flg = 1;
			} else {
				continue;
			}
		}
		mg(eg[i].x, eg[i].y);
		int l = i + 1, r = tot;
		while(l < r){
			int mid = l + r + 1 >> 1;
			if(chk(i, eg[mid].val)){
				l = mid;
			} else {
				r = mid - 1;
			}
		}
		if(chk(i, l)){
			ans = min(ans, eg[i].val + eg[l].val);
		}
		if(flg){
			break;
		}
	}
	printf("%d\n", ans);
	return 0;
}