PUTNIK

#include<stdio.h>
#include<iostream>
#include<set>
#include<map>
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
#include <iomanip>

#define sc scanf
#define pr printf
#define fr first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
const int MN = 1510;
const int INF = 10000010;
const double eps = 1e-12;

int n, len[MN][MN], d[MN][MN];

main(){
    //freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    sc("%d", &n);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            sc("%d", len[i]+j);
        }
    }
    d[1][2] = len[1][2];
    d[2][1] = len[2][1];
    int ans = INF;
    for(int i=3; i<=n; i++){
        d[i][i-1] = d[i-1][i] = INF;
        for(int j=1; j<i-1; j++){
            d[i][j] = d[i-1][j]+len[i][i-1];
            d[j][i] = d[j][i-1]+len[i-1][i];
            d[i][i-1] = min(d[i][i-1], d[j][i-1]+len[i][j]);
            d[i-1][i] = min(d[i-1][i], d[i-1][j]+len[j][i]);
        }
    }
    for(int j=1; j<n; j++){
        ans = min(ans, min(d[n][j], d[j][n]));
    }
    pr("%d\n", ans);
    return 0;
}