#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <cassert>
#include <string>
#include <memory.h>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <cctype>
#include <iomanip>
#include <sstream>
#include <cctype>
#include <fstream>
#include <cmath>
using namespace std;

#define REP2(i, m, n) for(ll i = (ll)(m); i < (ll)(n); i++)
#define REP(i, n) REP2(i, 0, n)
#define ALL(c) (c).begin(), (c).end()
#define ITER(c) __typeof((c).begin())
#define PB(e) push_back(e)
#define FOREACH(i, c) for(ITER(c) i = (c).begin(); i != (c).end(); ++i)
#define MP(a, b) make_pair(a, b)
#define PARITY(n) ((n) & 1)

typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1000 * 1000 * 1000 + 7;
const double EPS = 1e-10;

class MinCostFlow{
  typedef pair<ll, ll> P;
  class edge{
  public:
    ll to, cap, cost, rev;
    edge(){}
    edge(ll to, ll cap, ll cost, ll rev) : to(to),cap(cap),cost(cost),rev(rev){}
  };
  
  ll infinity;
  ll SIZE;
  vector<ll> dist;
  vector<ll> h;
  vector<ll> prevv;
  vector<ll> preve;
  vector<vector<edge> > G;
public:
  MinCostFlow(ll V) : SIZE(V),dist(vector<ll>(V)),h(vector<ll>(V)),
		       prevv(vector<ll>(V)), preve(vector<ll> (V)), 
		       G(vector<vector<edge> >(V)){ 
    infinity = 1000 * 1000 * 1000 + 7;
  }
  void add_edge(ll from, ll to, ll cap, ll cost){
    G[from].push_back(edge(to, cap, cost, G[to].size()));
    G[to].push_back(edge(from, 0, -cost, G[from].size()-1));
  }
  void init(ll size = 0){
    if(size > 0){
      dist.resize(size);
      h.resize(size);
      prevv.resize(size);
      preve.resize(size);
      G.resize(size);
    }
    for(ll i = 0; i < (ll)G.size(); i++) G[i].clear();
  }
  
  ll min_cost_flow(ll s, ll t, ll f){
    ll res = 0;
    fill(h.begin(), h.end(), 0);
    while(f > 0){
      priority_queue<P, vector<P>, greater<P> > que;
      fill(dist.begin(), dist.end(), infinity);
      dist[s] = 0;
      que.push(P(0, s));
      while(!que.empty()){
	P p = que.top(); que.pop();
	ll v  = p.second;
	if(dist[v] < p.first) continue;
	for(ll i =  0; i < (ll)G[v].size(); i++){
	  edge &e = G[v][i];
	  if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
	    dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
	    prevv[e.to] = v;
	    preve[e.to] = i;
	    que.push(P(dist[e.to], e.to));
	  }
	}
      }
      
      if(dist[t] == infinity) return -1;
      for(ll v = 0; v < SIZE; v++) h[v] += dist[v];
      
      ll d = f;
      for(ll v = t; v != s; v = prevv[v]){
	d = min(d, G[prevv[v]][preve[v]].cap);
      }
      f -= d;
      res += d * h[t];
      for(ll v = t; v != s; v = prevv[v]){
	edge &e = G[prevv[v]][preve[v]];
	e.cap -= d;
	G[v][e.rev].cap += d;
      }
    }
    return res;
  }
};


int main(){
  ll n;
  cin >> n;
  vector<vector<ll> > C(n, vector<ll>(n, 0));
  REP(i, n) REP(j, n) cin >> C[i][j];
  ll s = 2 * n;
  ll t = s + 1;
  MinCostFlow mcf(2 * n + 2);
  ll S = 0;

  REP(i, n)REP(j, i){
    ll tmp = min(C[i][j], C[j][i]);
    S += tmp;
    C[i][j] -= tmp;
    C[j][i] -= tmp;
  }

  REP(i, n){
    mcf.add_edge(s, i, 1, 0);
    mcf.add_edge(i + n, t, 1, 0);
  }
  
  REP(i, n)REP(j, n){
    mcf.add_edge(i, j + n, 1, C[i][j]);
  }
  cout << S + mcf.min_cost_flow(s, t, n - 1) << endl;
  return 0;
}

Measured memory_bytes: 2128