#include <bits/stdc++.h>
using namespace std;
const int INF=2e9;
int n,d[201][201],sz[201],len[401][401],res=INF;
pair <int, int> p[201];
vector <int> v;
vector <pair <int, int>> ve[20000];
void update(int a, int b, int w){
    for (int i=1;i<=n*2;i++)
        for (int j=1;j<=n*2;j++)
            len[i][j]=max(len[i][j],min(min((i==a?INF:len[i][a]),(j==b?INF:len[b][j])),w));
}
pair <int, int> f(int i){
    if (p[i].first!=i){
        int tmp=p[i].second;
        p[i]=f(p[i].first);
        p[i].second^=tmp;
    }
    return p[i];
}
bool unite(int i, int j, int w){
    auto x=f(i);
    auto y=f(j);
    if (x.first==y.first)
        return (x.second!=y.second);
    if (sz[x.first]<sz[y.first])
        swap(x,y);
    p[y.first]={x.first,x.second^y.second^1};
    sz[x.first]+=sz[y.first];
    update(j+n,i,w);
    update(i+n,j,w);
    return true;
}
int main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n;
    for (int i=1;i<=n;i++){
        p[i].first=i;
        sz[i]=1;
    }
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++){
            cin >> d[i][j];
            d[j][i] = d[i][j];
        }
    for (int k = 1; k <= n; ++k) {
        for (int u = 1; u <= n; ++u) {
            for (int v = 1; v <= n; ++v) {
                d[u][v] = min(d[u][v], d[u][k] + d[k][v]);
            }
        }
    }
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++){
            v.push_back(d[i][j]);
        }
    v.push_back(0);
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end())-v.begin());
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++){
            d[i][j]=lower_bound(v.begin(),v.end(),d[i][j])-v.begin();
            ve[d[i][j]].push_back({i,j});
            len[i][j+n]=max(len[i][j+n],d[i][j]);
            len[j][i+n]=max(len[j][i+n],d[i][j]);
        }
    for (int k=1;k<=n*2;k++)
        for (int i=1;i<=n*2;i++)
            for (int j=1;j<=n*2;j++)
                len[i][j]=max(len[i][j],min(len[i][k],len[k][j]));
    for (int i=v.size()-1;i>=0;i--){
        int mx=0;
        for (int i=1;i<=n;i++)
            mx=max(mx,min(len[i][i+n],len[i+n][i]));
        res=min(res,v[i]+v[mx]);
        int ch=1;
        for (auto [u,v]:ve[i])
            if (!unite(u,v,i)){
                ch=0;
                break;
            }
        if (!ch)
            break;
    }
    cout << res;
}