#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

ifstream f("cc.in");
ofstream g("cc.out");

int N, S, T, dist;
vector<vector<int>> list, cap, flow, distanta;
vector<int> previous, distantaMin;
int res;

int bfs () {
    // gasim un drum de la S la T

    fill(previous.begin(), previous.end(), -1);
    fill(distantaMin.begin(), distantaMin.end(), INT_MAX);

    distantaMin[0] = 0;
    queue<pair<int, int>> q;
    q.push({0, INT_MAX});

    while (!q.empty()) {
        int cur = q.front().first, minFlowUntilNow = q.front().second;
        q.pop();
        for (auto& next : list[cur]) {

            if (distantaMin[next] > distantaMin[cur] + distanta[cur][next] && cap[cur][next] > flow[cur][next]) {
                previous[next] = cur;
                int residual_cap = cap[cur][next] - flow[cur][next];
                int nextMinFlow = residual_cap > minFlowUntilNow ? minFlowUntilNow : residual_cap;
                distantaMin[next] = distantaMin[cur] + distanta[cur][next];
                q.push({next, nextMinFlow});
            }
        }
    }

    return previous[T] >= 0;
}

void edmonds_karp () {
    while (true) {
        int flow_of_path = bfs();

        if (!flow_of_path) break; // nu a fost gasit niciun augmented path (de la S la T)

        // in cazul in care a fost gasit, refacem drumul si updatam flow-ul pe tot drumul
        int cur = T;
        while (cur != 0) {
            int prevNode = previous[cur];
            flow[prevNode][cur] += flow_of_path;
            flow[cur][prevNode] -= flow_of_path;
            cur = prevNode;
        }

        res += distantaMin[T];
    }
    g << res;
}

int main () {
    f >> N;
    T = 2 * N + 1;
    previous.resize(T + 1);
    distantaMin.resize(T + 1);
    list.resize(T + 1, {});
    cap.assign(T + 1, vector<int>(T + 1, 0));
    flow.resize(T + 1, vector<int>(T + 1, 0));
    distanta.resize(T + 1, vector<int>(T + 1, 0));

    for (int i = 1; i <= N; i++) {
        list[0].push_back(i);
        list[i].push_back(0);
        cap[0][i] = 1;

        for (int j = 1; j <= N; j++) {
            f >> dist;
            list[i].push_back(j + N);
            list[j + N].push_back(i);
            cap[i][j + N] = 1;
            distanta[i][j + N] = dist;
            distanta[j + N][i] = -dist;
        }
    }

    for (int i = 1; i <= N; i++) {
        list[i + N].push_back(T);
        list[T].push_back(i + N);
        cap[i + N][T] = 1;
    }

    edmonds_karp();

    g << "Suma minima a distantelor: " << res << endl;

    return 0;
}