#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
vector<vector<int>> a(n, vector<int>(n));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> a[i][j];
}
}
if (n == 1)
{
cout << 0 << '\n';
return 0;
}
vector<vector<long long>> dp(n, vector<long long>(n, INF)),
dp2(n, vector<long long>(n, INF));
function<void(int, int)> solve = [&](int l, int r)
{
if (l + 2 == r)
{
dp[l][r - 1] = dp[r - 1][l] = a[l][r - 1];
return;
}
int mid = (l + r) / 2;
solve(l, mid);
solve(mid, r);
// for (int i1 = l; i1 < (l + mid) / 2; i1++)
// {
// for (int j1 = (l + mid) / 2; j1 < mid; j1++)
// {
// for (int i2 = mid; i2 < (mid + r) / 2; i2++)
// {
// for (int j2 = (mid + r) / 2; j2 < r; j2++)
// {
// dp[i1][i2] = min(dp[i1][i2], dp[i1][j1] + a[j1][j2] + dp[j2][i2]);
// dp[i2][i1] = min(dp[i2][i1], dp[i1][i2]);
// dp[i1][j2] = min(dp[i1][j2], dp[i1][j1] + a[j1][i2] + dp[i2][j2]);
// dp[j2][i1] = min(dp[j2][i1], dp[i1][j2]);
// dp[j1][i2] = min(dp[j1][i2], dp[j1][i1] + a[i1][j2] + dp[j2][i2]);
// dp[i2][j1] = min(dp[i2][j1], dp[j1][i2]);
// dp[j1][j2] = min(dp[j1][j2], dp[j1][i1] + a[i1][i2] + dp[i2][j2]);
// dp[j2][j1] = min(dp[j2][j1], dp[j1][j2]);
// }
// }
// }
// }
for (int i = l; i < (l + mid) / 2; i++)
{
for (int j = (l + mid) / 2; j < mid; j++)
{
for (int k = mid; k < r; k++)
{
dp2[i][k] = min(dp2[i][k], dp[i][j] + a[j][k]);
dp2[j][k] = min(dp2[j][k], dp[j][i] + a[i][k]);
}
}
}
for (int i = l; i < mid; i++)
{
for (int j = mid; j < (mid + r) / 2; j++)
{
for (int k = (mid + r) / 2; k < r; k++)
{
dp[i][k] = min(dp[i][k], dp2[i][j] + dp[j][k]);
dp[i][j] = min(dp[i][j], dp2[i][k] + dp[k][j]);
}
}
}
for (int i = l; i < mid; i++)
{
for (int j = mid; j < r; j++)
{
dp[j][i] = min(dp[j][i], dp[i][j]);
}
}
};
solve(0, n);
long long ans = INF;
for (int i = 0; i < n / 2; i++)
{
for (int j = n / 2; j < n; j++)
{
ans = min(ans, dp[i][j]);
ans = min(ans, dp[j][i]);
}
}
cout << ans << '\n';
return 0;
}
