/*

HDU 4370 0 or 1

转换思维的题啊，由一道让人不知如何下手的题，转换为了最短路

基本思路就是把矩阵看做一个图，图中有n个点，1号点出度为1，

n号点入度为1，其它点出度和入度相等，路径长度都是非负数，

等价于一条从1号节点到n号节点的路径，故Xij=1表示需要经

过边(i,j)，代价为Cij。Xij=0表示不经过边(i,j)。注意到Cij非负

且题目要求总代价最小，因此最优答案的路径一定可以对应一条简单路径。

最终，我们直接读入边权的邻接矩阵，跑一次1到n的最短路即可，记最短路为path。

漏了如下的情况B：

从1出发，走一个环（至少经过1个点，即不能

是自环），回到1；从n出发，走一个环（同理），回到n。

也就是1和n点的出度和入度都为1，其它点的出度和入度为0.

由于边权非负，于是两个环对应着两个简单环。

因此我们可以从1出发，找一个最小花费环，记代价为c1,

再从n出发，找一个最小花费环，记代价为c2。

（只需在最短路算法更新权值时多加一条记录即可：if(i==S) cir=min(cir,dis[u]+g[u][i])）

故最终答案为min(path,c1+c2)

*/

/*

本程序用SPFA来完成最短路。

但是由于要计算从出发点出发的闭环的路径长度。

所以要在普通SPFA的基础上做点变化。

就是把dist[start]设为INF。同时一开始并不是让出发点入队，而是让

出发点能够到达的点入队。

*/

//以上来自kuangbin的blog

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include <queue>

#include <vector>

#include<bitset>

using namespace std;

typedef long long LL;

const int maxn = ;

const int mod = +;

typedef pair<int,int> pii;

#define X first

#define Y second

#define pb push_back

//#define mp make_pair

#define ms(a,b) memset(a,b,sizeof(a))

const int inf = 0x3f3f3f3f;

int cost[maxn][maxn];

int dist[maxn];

int que[maxn];

bool vis[maxn];

void spfa(int st,int n){

    int fro =  ,rear = ;

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

        if(i==st){

            dist[i]=inf;

            vis[i]=false;

        }else if(cost[st][i]!=inf){

            dist[i]=cost[st][i];

            que[rear++]=i;

            vis[i]=true;

        }else{

            dist[i]=inf;

            vis[i]=false;

        }

    }

    while(fro!=rear){

        int u = que[fro++];

        for(int v=;v<=n;v++){

            if(dist[v]>dist[u]+cost[u][v]){

                dist[v]=dist[u]+cost[u][v];

                if(!vis[v]){

                    vis[v]=true;

                    que[rear++]=v;

                    if(rear>=maxn) rear=;

                }

            }

        }

        vis[u]=false;

        if(fro>=maxn) fro=;

    }

}

int main(){

    int n;

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

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

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

                scanf("%d",&cost[i][j]);

            }

        }

        spfa(,n);

        int ans=dist[n];

        int loop1=dist[];

        spfa(n,n);

        int loop2=dist[n];

        ans=min(ans,loop1+loop2);

        cout<<ans<<endl;

    }

}