#include <stdio.h>

int N, M[124][124], v[124], d[124], S[124];

int main(void)
{
    int i, j, k, S1, i1, i2;
    
    freopen("cc.in", "r", stdin);
    freopen("cc.out", "w", stdout);
    
    scanf("%d", &N);
    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
            scanf("%d", &M[i][j]);
            
    S[1] = M[1][1]; d[1] = 1; v[1] = 1;
    for (k = 2; k <= N; k++)
    {
        S[k] = S[k-1] + M[k][k]; d[k] = k; v[k] = k;
        
        for (i = 1; i < k; i++)
            if (S[k] > S[k-1] - M[i][d[i]] + M[i][k] + M[k][d[i]])
               S[k] = S[k-1] - M[i][d[i]] + M[i][k] + M[k][d[i]],
               d[k] = d[i],
               v[k] = i;
        
        for (i = 1; i < k; i++)
            for (j = 1; j < k; j++)
                if (d[i] != j)
                {
                   S1 = S[k-1] - M[i][d[i]] - M[v[j]][j] + M[i][k] + M[k][j] + 
                        M[v[j]][d[i]];
                   if (S[k] > S1)
                      S[k] = S1, i1 = v[j], i2 = d[i],
                      d[i1] = i2, d[i] = k, d[k] = j,
                      v[i2] = i1, v[k] = i, v[j] = k;
                      
                }
                   
    }
        
    printf("%d\n", S[N]);
    
    return 0;
}