//ZAD5: Zadatak je travelling salesman problem sa specificnim zahtjevom. Rjesenje koristi tehniku dinamickog programiranja (Dynamic Programming)

#include <iostream>
#include <algorithm>

int n;
int a[1510][1510];
int memo[1510][1510];

int dp(int l, int r) {
  if (memo[l][r]) return memo[l][r];
  int next = std::max(l, r) + 1;
  if (next == n) return 0;
  return memo[l][r] = std::min(a[next][l] + dp(next, r), a[r][next] + dp(l, next));
}

int main () {
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            std::cin >> a[i][j];
    
    std::cout << dp(0, 0);
}
