#include<cstdio>

#include<algorithm>

#define N 205

using namespace std;

typedef unsigned long long ll;

int n,m,i,j,k,t,q[N<<1],f[N<<1],ans;

struct E{int x,y,w;E(){}E(int _x,int _y,int _w){x=_x,y=_y,w=_w;}}e[N*N];

inline bool cmp(const E&a,const E&b){return a.w<b.w;}

struct BIT{

  ll v[4];

  void clear(){for(int i=0;i<4;i++)v[i]=0;}

  void flip(int x){v[x>>6]^=1ULL<<(x&63);}

  int get(int x){return v[x>>6]>>(x&63)&1;}

}v0,v1,g0[N<<1],g1[N<<1];

inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';}

inline void addA(int x,int y){

  g0[x].flip(y);

  g1[y+n].flip(x);

  g0[y].flip(x);

  g1[x+n].flip(y);

}

inline void addB(int x,int y){

  g0[x+n].flip(y);

  g1[y].flip(x);

  g0[y+n].flip(x);

  g1[x].flip(y);

}

void dfs1(int x){

  if(x<n){

    v0.flip(x);

    for(int i=0;i<4;i++)while(1){

      ll o=v1.v[i]&g0[x].v[i];

      if(!o)break;

      dfs1((i<<6|__builtin_ctzll(o))+n);

    }

  }else{

    v1.flip(x-n);

    for(int i=0;i<4;i++)while(1){

      ll o=v0.v[i]&g0[x].v[i];

      if(!o)break;

      dfs1(i<<6|__builtin_ctzll(o));

    }

  }

  q[++t]=x;

}

void dfs2(int x,int y){

  f[x]=y;

  if(x<n){

    v0.flip(x);

    for(int i=0;i<4;i++)while(1){

      ll o=v1.v[i]&g1[x].v[i];

      if(!o)break;

      dfs2((i<<6|__builtin_ctzll(o))+n,y);

    }

  }else{

    v1.flip(x-n);

    for(int i=0;i<4;i++)while(1){

      ll o=v0.v[i]&g1[x].v[i];

      if(!o)break;

      dfs2(i<<6|__builtin_ctzll(o),y);

    }

  }

}

inline bool check(){

  int i;

  v0.clear(),v1.clear();

  for(i=0;i<n;i++)v0.flip(i),v1.flip(i);

  for(t=i=0;i<n;i++)if(v0.get(i))dfs1(i);

  for(i=0;i<n;i++)if(v1.get(i))dfs1(i+n);

  for(i=0;i<n;i++)v0.flip(i),v1.flip(i);

  for(i=t;i;i--)if(q[i]<n){if(v0.get(q[i]))dfs2(q[i],q[i]);}else if(v1.get(q[i]-n))dfs2(q[i],q[i]);

  for(i=0;i<n;i++)if(f[i]==f[i+n])return 0;

  return 1;

}

void solve(){

  ans=~0U>>1;

  sort(e+1,e+m+1,cmp);

  for(i=0;i<n+n;i++)g0[i].clear(),g1[i].clear();

  for(i=1;i<=m;i++)addA(e[i].x,e[i].y);

  for(i=0,j=m;i<=j;i++){

    if(i)addA(e[i].x,e[i].y);

    while(e[i].w+e[j].w>=ans||check()){

      ans=min(ans,e[i].w+e[j].w);

      if(j)addB(e[j].x,e[j].y);

      if((--j)<i)return;

    }

  }

}

int main(){

  while(~scanf("%d",&n)){

    for(m=i=0;i<n;i++)for(j=i+1;j<n;j++)read(k),e[++m]=E(i,j,k);

    solve();

    printf("%d\n",ans);

  }

  return 0;

}