#include "bits/stdc++.h"
using namespace std;
#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif
const int N = 2050;
const long long INF = 1e15;
int a[N][N];
long long dp[N][N];
long long ndp[N][N];
long long dp2[N][N];
void solve(int l, int r) {
if (l + 1 == r) {
dp[l][r] = dp[r][l] = a[l][r];
return;
}
int mid = (l + r) / 2;
solve(l, mid);
solve(mid + 1, r);
for (int i = l; i <= r; ++i) {
for (int j = l; j <= r; ++j) {
ndp[i][j] = ndp[j][i] = INF;
dp2[i][j] = dp2[j][i] = INF;
}
}
for (int i = l; i <= mid; ++i) {
for (int j = mid + 1; j <= r; ++j) {
for (int k = l; k <= mid; ++k) {
if (k == i) continue;
dp2[i][j] = min(dp2[i][j], dp[i][k] + a[j][k]);
}
for (int k = mid + 1; k <= r; ++k) {
if (k == j) continue;
ndp[i][k] = min(ndp[i][k], dp2[i][j] + dp[j][k]);
}
}
}
for (int i = l; i <= mid; ++i) {
for (int j = mid + 1; j <= r; ++j) {
dp[i][j] = dp[j][i] = ndp[i][j];
}
}
for (int i = l; i <= mid; ++i) {
for (int j = l; j <= mid; ++j) {
dp[i][j] = INF;
}
}
for (int i = mid + 1; i <= r; ++i) {
for (int j = mid + 1; j <= r; ++j) {
dp[i][j] = INF;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> a[i][j];
}
}
solve(1, n);
long long ans = INF;
for (int i = 1; i <= n / 2; ++i) {
for (int j = n / 2 + 1; j <= n; ++j) {
ans = min(ans, dp[i][j]);
ans = min(ans, dp[j][i]);
}
}
cout << ans << '\n';
return 0;
}
