#define _CRT_SECURE_NO_WARNINGS
#define INF 10e9
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <queue>
#include <stack>
#include <climits>
using namespace std;

vector <vector<int>> mas;
vector <vector<int>> mas2;

vector<int> a;
vector<int> a1;
vector<int> a2;
vector<int> u;
queue<int> Queue;

int n,k, w = 0,sum = 0,n1,q,v;
bool f = false;

void poisk_sh() {
    a1[1] = 0;
    Queue.push(1);

    while (!Queue.empty())
    {
        int m = Queue.front();
        Queue.pop();
        for (int i = 1; i <= n; i++) {
            if ((mas[m][i] != 0) && (a1[i] == -1) && (i != m)) {
                a1[i] = a1[m] + 1;
                Queue.push(i);
                a2[i] = m;
            }
        }
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> n;


    mas.resize(n+1);
    mas2.resize(n+1);
    for (long i = 1; i < n+1; i++)
    {
        mas[i].resize(n+1);
        mas2[i].resize(n+1);
    }
    n1 = n;
    a.resize(n + 1);
    a1.resize(n + 1);
    a2.resize(n + 1);
    u.resize(n + 1);



    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            cin >> mas[i][j];
            mas2[i][j] = 0;
        }

    while (f != true) {

        for (int i = 1; i <= n; i++) {
            a1[i] = -1;
            a2[i] = -1;
        }
        poisk_sh();

        if (a1[n] == -1) break;

        else {
           q = v= a1[n];
           u[v] = n;
           k = a2[n];
            while (a2[n] != -1) {
                v--;
                n = a2[n];
                u[v] = n;
            }
            int minimum = INT_MAX;
            for (int i = 0; i < q; i++) {
                if (mas[u[i]][u[i + 1]] < minimum) {
                    minimum = mas[u[i]][u[i + 1]];
                }
            }
            a[w] = minimum;

            for (int i = 0; i < q; i++) {
                mas[u[i]][u[i + 1]] = mas[u[i]][u[i + 1]] - a[w];
                mas2[u[i]][u[i + 1]] = mas2[u[i]][u[i + 1]] + a[w];
            }
            n = n1;
            sum = sum + a[w];
            w++;
        }
    }
    cout << sum;
    return 0;
}