RT

#include <bits/stdc++.h>

#define FstIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pb push_back
#define mem(a, v) memset(a, v, sizeof a)

using namespace std;
using ll = int;
using ull = unsigned long long;
 
const ll N = 20, M = 20;
const ll mod = 998244353, mod2 = 1e9 + 7;

ll n;

ll dis[N][N];

ll dp[1 << M][N];

//dp[S][i]
//Statu = S, Stay at i

void Floyd()
{
	for (ll k = 0; k < n; k ++ )
	{
		for (ll i = 0; i < n; i ++ )
		{
			if (i == k) continue;
			for (ll j = 0; j < n; j ++ )
			{
				if (i == j) continue;
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
}

void sol()
{
	cin >> n;
//	mem(dis, 0x3f3f3f3f);
	for (ll i = 0; i < n; i ++ )
		for (ll j = 0; j < n; j ++ ) 
			cin >> dis[i][j];
	Floyd();
	mem(dp, 0x3f3f3f3f);
	dp[0][0] = 0; 
	for (ll i = 0; i < n; i ++ )
	{
		dp[1 << i][i] = dis[0][i];
	}
	for (ll S = 0; S < (1 << n); S ++ )
	{
		for (ll i = 0; i < n; i ++ )
		{
			if ((S >> i) & 1) 
			{
				for (ll j = 0; j < n; j ++ )
				{
					if (i == j) continue;
					if ((S >> j) & 1)
						dp[S][i] = min(dp[S][i], dp[S - (1 << i)][j] + dis[j][i]);
				}
			}
		}
	}
	
	cout << dp[(1 << n) - 1][0] << '\n';
}

signed main()
{
	srand(time(0));
	clock_t st = clock();
	
	FstIO;
	
	ll t = 1;
//	cin >> t;
	while (t -- ) sol();
	
	clock_t en = clock();
//	cout << '\n' << (double)(en - st) / (CLOCKS_PER_SEC) << '\n';
}