//采取逆向思维，从n倒着搜；

#include<bits/stdc++.h>

#define int long long

using namespace std;

struct node

{

    int next,to,dis;

}edge[50005];

int head[50005],n,cnt;

inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}

    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

inline void add(int from,int to,int dis)

{

    edge[++cnt].next=head[from];

    edge[cnt].to=to;

    edge[cnt].dis=dis;

    head[from]=cnt;

}

int dis[105],vis[105];//dis[i]即从i到n的所需最少的细菌数

void work()

{

    queue<int> q;

    dis[n]=1;vis[n]=1;q.push(n);

    while(!q.empty())

    {

        int now=q.front();q.pop();vis[now]=0;

        for (int i=head[now];i;i=edge[i].next)

        {

            int to=edge[i].to;

            if (dis[to]>max((long long)1,(dis[now]+edge[i].dis+1)/2))

            {

                dis[to]=max((long long)1,(dis[now]+edge[i].dis+1)/2);

                if (!vis[to])

                {

                    q.push(to);

                    vis[to]=1;

                }

            }

        }

    }

}

signed main()

{

    n=read();

    for (int i=1;i<=n;i++) dis[i]=0x3f3f3f3f;

    for (int i=1;i<=n;i++)

        for (int j=1;j<=n;j++)

        {

            int d=read();

            if (d!=0) add(j,i,-d);//反向存图

        }

    work();

    printf("%ld",dis[1]);

    return 0;

}