#include <stdio.h>

#define nm 120

long long a[nm][nm], d[nm], v[nm];

long long n, i, j, s, x, C, l, R, k, y, z;

void read()

{
	scanf("%lld", &n);
    for (i=1; i<=n; i++)
    	for (j=1; j<=n; j++)
    	{
    		scanf("%lld", &a[i][j]);
    	}
}

void solve()

{
	d[1] = 1;
	v[1] = 1;
	s = a[1][1];
    
	for (k = 2; k <= n; k++)
    {
    	l = a[1][k] + a[k][d[1]] - a[1][d[1]];
    	x = 1;
    	C = d[x];
    	j = d[x];
        
    	for (i = 1; i < k; i++)
        {
    		j = d[i];
    		R = a[i][k] + a[k][j] - a[i][j];
    		if (R < l)
            {
    			l = R;
    			x = i;
    			j = d[i];
    			C = j;
    			y = j;
    		}
    		for (int c = 1; c < k; c++)
    			if (c - j)
                {
    				int u = v[c];
    				R = a[i][k] + a[k][c] -	a[i][j] - a[u][c] + a[u][j];
    				if (R < l)
                    {
    					l = R;
    					C = c;
    					x = i;
    					z = u;
    					y = j;
					}
				}
		}
        
		if (l >= a[k][k])
        {
			s += a[k][k];
			d[k] = k;
			v[k] = k;
		}
		else
        {
			s += l;
			if (C == y)
            {
				d[x] = k;
				d[k] = C;
				v[C] = k;
				v[k] = x;
			}
			else
            {
				d[x] = k;
				v[k] = x;
				d[z] = y;
				v[y] = z;
				d[k] = C;
				v[C] = k;
			}
		}
	}
}



void write()

{
	printf("%lld\n", s);
}


int main()

{
	freopen("cc.in", "r", stdin);
    freopen("cc.out","w",stdout);

    read();
    solve();
    write();

    fclose(stdin);
    fclose(stdout);

	return 0;
}