//
// Created by liasa on 29/01/2026.
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (ll i = s; i < e; ++i)
ll n;
ll adj[2050][2050];
struct node {
v<ll> ind;
v<ll> l, r;
};
node solve(ll s, ll e) {
if (s == e)
return {{s}, {0}, {0}};
ll mid = (s + e) / 2;
node a = solve(s, mid);
node b = solve(mid + 1, e);
ll c1 = 2e18, c2 = 2e18;
lp(i, 0, a.ind.size()) {
lp(j, 0, b.ind.size()) {
c1 = min(c1, a.r[i] + b.l[j] + adj[a.ind[i]][b.ind[j]]);
}
}
lp(i, 0, b.ind.size()) {
lp(j, 0, a.ind.size()) {
c2 = min(c2, b.r[i] + a.l[j] + adj[b.ind[i]][a.ind[j]]);
}
}
node res;
lp(i, 0, a.ind.size()) {
res.ind.push_back(a.ind[i]);
res.l.push_back(a.l[i]);
res.r.push_back(a.r[i] + c2);
}
lp(i, 0, b.ind.size()) {
res.ind.push_back(b.ind[i]);
res.l.push_back(b.l[i]);
res.r.push_back(b.r[i] + c1);
}
if (res.ind.size() == n) {
ll min_ar = 2e18, min_br = 2e18;
for (ll x : a.r)
min_ar = min(min_ar, x);
for (ll x : b.r)
min_br = min(min_br, x);
cout << min(c1 + min_br, c2 + min_ar) << endl;
}
return res;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
lp(i, 0, n) {
lp(j, 0, n) { cin >> adj[i][j]; }
}
if (n == 1) {
cout << 0 << endl;
return 0;
}
solve(0, n - 1);
}
