#include<bits/stdc++.h>
using namespace std;
int a[17][17],dp[50001][17];
int ans=1000001,n;
inline const void read(int &a){
	a=0;
	char c=getchar();
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9')
	{
		a=(a<<1)+(a<<3)+c-'0';
		c=getchar();
	}
}
int min(int a,int b)
{
	if(a==-1) return b;
	if(b==-1) return a;
	return a<b?a:b;
}
int main()
{
	read(n);
	n++;
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	read(a[i][j]);
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	for(int k=0;k<n;k++)
	if(a[j][i]+a[i][k]<a[j][k])
	a[j][k]=a[j][i]+a[i][k];
	dp[1][0]=0;
	for(int i=0;i<(1<<n);i++)
	for(int j=0;j<n;j++)
	    if(dp[i][j]!=-1)
	    for(int k=0;k<n;k++)
		    if(!i&(1<<k))
	    	{
		    	dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+a[j][k]);
		    	if((i|(1<<k))==((1<<n)-1))
		    	ans=min(ans,dp[i|1<<k][k]);
	    	}
    cout<<ans<<endl;
    return 0;
}