#include <stdio.h>

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

int main(void)
{
    int i, j, k, S1, SMIN, i1, i2, tp, si, sj;
    
    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++)
    {
        SMIN = S[k-1] + M[k][k]; tp = 0;
        
        for (i = 1; i < k; i++)
            if (SMIN > S[k-1] - M[i][d[i]] + M[i][k] + M[k][d[i]])
               SMIN = S[k-1] - M[i][d[i]] + M[i][k] + M[k][d[i]],
               tp = 1, si = 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 (SMIN > S1)
                      SMIN = S1, tp = 2, si = i, sj = j;                      
                }
       
        S[k] = SMIN;
        if (tp == 0)
             d[k] = k, v[k] = k;
        else if (tp == 1)
             i = si, i1 = d[i],
             d[k] = i1, d[i] = k,
             v[i1] = k, v[k] = i;
        else if (tp == 2)
             i = si, j = sj,
             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;
}