#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;
return 0;
}