#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define intt long long
#define pb push_back
vector<vector<int>> mat;
int n ;
const intt INF = 1e18;
vector<vector<intt>> dp , dp_;
void solve(int l , int r)
{
if(l + 1 == r)
{
dp[l][r] = dp[r][l] = mat[l][r];
return ;
}
int m = (l + r)/2;
solve(l , m);
solve(m + 1, r);
for(int i = l ; i <= m ; i++)
{
for(int j1 = m + 1 ; j1 <= (m + 1 + r)/2 ; j1++)
{
for(int j2 = (m + 1 + r)/2 + 1; j2 <= r ; j2++)
{
dp_[i][j1] = min(dp_[i][j1] , dp[j1][j2] + mat[j2][i]);
dp_[i][j2] = min(dp_[i][j2] , dp[j1][j2] + mat[j1][i]);
}
}
}
for(int i1 = l ; i1 <= (l + m)/2 ; i1++)
{
for(int i2 = (l + m)/2 + 1 ; i2 <= m ; i2++)
{
for(int j = m + 1 ; j <= r ; j++)
{
dp[i1][j] = min(dp[i1][j] , dp_[i2][j] + dp[i1][i2]);
dp[i2][j] = min(dp[i2][j] , dp_[i1][j] + dp[i1][i2]);
}
}
}
for(int i = l ; i <= m ; i++)
{
for(int j = m + 1 ; j <= r ; j++)
{
dp[j][i] = dp[i][j];
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
mat = vector<vector<int>> (n , vector<int>(n));
dp.assign(n , vector<intt>(n , INF));
dp_ = dp;
for(int i = 0 ; i < n ; i++)
{
for(int j = 0 ; j < n ; j++)
{
cin>>mat[i][j];
}
}
if(n == 1)
{
cout<<0<<'\n';
return 0;
}
intt ans = INF;
solve(0 ,n - 1);
int l = 0 , r = n - 1;
int m = (l + r)/2;
for(int fr = l ; fr <= m ; fr++)
{
for(int bk = m + 1 ; bk <= r ; bk++)
{
ans = min({ans , dp[fr][bk] , dp[bk][fr]});
}
}
cout<<ans<<'\n';
}
