#include <iostream>

#include <ios>

#include <iomanip>

#include <functional>

#include <algorithm>

#include <vector>

#include <sstream>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <string>

#include <set>

#include <map>

#include <cstdio>

#include <cstdlib>

#include <cctype>

#include <cmath>

#include <cstring>

#include <climits>

using namespace std;

#define XINF INT_MAX

#define INF 1<<30

#define MAXN 300+10

#define eps 1e-8

#define zero(a) fabs(a)<eps

#define sqr(a) ((a)*(a))

#define MP(X,Y) make_pair(X,Y)

#define PB(X) push_back(X)

#define PF(X) push_front(X)

#define REP(X,N) for(int X=0;X<N;X++)

#define REP2(X,L,R) for(int X=L;X<=R;X++)

#define DEP(X,R,L) for(int X=R;X>=L;X--)

#define CLR(A,X) memset(A,X,sizeof(A))

#define IT iterator

#define PI  acos(-1.0)

#define test puts("OK");

#define _ ios_base::sync_with_stdio(0);cin.tie(0);

typedef long long ll;

typedef pair<int,int> PII;

typedef priority_queue<int,vector<int>,greater<int> > PQI;

typedef vector<PII> VII;

typedef vector<int> VI;

#define X first

#define Y second

int V,E;

int cost[MAXN][MAXN];

int d[MAXN];

bool inq[MAXN];

void SPFA(int s)

{

    queue<int> Q;

    REP(i,V)

    {

        if(i==s)

        {

            d[i]=INF;

            inq[i]=;

        }

        else

        {

            d[i]=cost[s][i];

            Q.push(i);

            inq[i]=;

        }

    }

    while(!Q.empty())

    {

        int u=Q.front();Q.pop();inq[u]=;

        REP(v,V)

        {

            if(d[v]>d[u]+cost[u][v])

            {

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

                if(!inq[v])

                {

                    Q.push(v);

                    inq[v]=;

                }

            }

        }

    }

} 

int main()

{_

    while(~scanf("%d",&V))

    {

        REP(i,V)

            REP(j,V)

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

        SPFA();

        int ans=d[V-],c1=d[];

        SPFA(V-);

        int c2=d[V-];

        printf("%d\n",min(ans,c1+c2));

    }

    return ;

}