#include <bits/stdc++.h>
using namespace std;
int n,ans=99999999;
int s[16][16];
int f[1<<16][16];

int Min(int x,int y)
{
	if(x==-1) return y;
	if(y==-1) return x;
	return x<y? x:y;
}
main()
{
	int i,j,k;
	cin>>n;
	n++;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			cin>>s[i][j];
	for(k=0;k<n;k++)
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				s[i][j]=min(s[i][j],s[i][k]+s[k][j]);
	memset(f,-1,sizeof(f));
	f[1][0]=0;
	for(i=1;i<(1<<n);i++)
		for(j=0;j<n;j++)//当前位置 
			if(f[i][j]!=-1)
				for(k=0;k<n;k++)//目标位置 
					if(!(i&(1<<k)))
					{
						f[i|(1<<k)][k]=Min(f[i|(1<<k)][k],f[i][j]+s[j][k]);
						if((i|(1<<k))==(1<<n)-1)
							ans=min(ans,f[i|(1<<k)][k]+s[k][0]);
					}
	cout<<ans;
}#include <bits/stdc++.h>
using namespace std;
int n,ans=99999999;
int s[16][16];
int f[1<<16][16];

int Min(int x,int y)
{
	if(x==-1) return y;
	if(y==-1) return x;
	return x<y? x:y;
}
main()
{
	int i,j,k;
	cin>>n;
	n++;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			cin>>s[i][j];
	for(k=0;k<n;k++)
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				s[i][j]=min(s[i][j],s[i][k]+s[k][j]);
	memset(f,-1,sizeof(f));
	f[1][0]=0;
	for(i=1;i<(1<<n);i++)
		for(j=0;j<n;j++)//当前位置 
			if(f[i][j]!=-1)
				for(k=0;k<n;k++)//目标位置 
					if(!(i&(1<<k)))
					{
						f[i|(1<<k)][k]=Min(f[i|(1<<k)][k],f[i][j]+s[j][k]);
						if((i|(1<<k))==(1<<n)-1)
							ans=min(ans,f[i|(1<<k)][k]+s[k][0]);
					}
	cout<<ans;
}