#include<iostream>
#include<cstdio>
#include<ctime>
#define INF 0x3f3f3f3f
#define N 20
using namespace std;
int dis[N],que[55],u[N],way[N][N][N],pre[N],juz[N][N],ndis[N][N];
int n,head,tail,ans=INF,sum,cnt;
void DFS(int x)
{
	cnt++;
	if(cnt>4000000) return ;
	int w;
	for(w=1;w<=n;w++)
	{
		//cout<<u[w]<<" ";
		if(u[w]==0) break;
		
	}
	//cout<<endl;
	//cout<<w<<" "<<x<<" "<<sum<<endl;
	if(w>n) 
	{
		//cout<<sum<<endl;
		ans=min(ans,sum+ndis[x][0]);
		//cout<<ans<<endl;
		return ;
	}
	for(int i=1;i<=n;i++)
	{
		if(!u[i])
		{
			//cout<<i<<endl;
			sum+=ndis[x][i];u[i]=1;
			if(sum>ans) 
			{
				u[i]=0;
				sum-=ndis[x][i];continue;
			}
			for(int j=1;j<=way[x][i][0];j++)
			{
				u[way[x][i][j]]=1;
			}
			DFS(i);
			for(int j=1;j<=way[x][i][0];j++)
			{
				u[way[x][i][j]]=0;
			}
			sum-=ndis[x][i];u[i]=0;
		}
	}
}
void SPFA(int x)
{
	
	for(int i=0;i<=n;i++)
	{
		dis[i]=INF;pre[i]=0;
	}
	head=0;tail=1;que[1]=x;u[x]=1;dis[x]=0;
	do
	{
		head++;
		head=(head-1)%50+1;
		int k=que[head];
		u[head]=0;
		for(int i=0;i<=n;i++)
		{
			if(dis[k]+juz[k][i]<dis[i])
			{
				dis[i]=dis[k]+juz[k][i];
				pre[i]=k;
				if(!u[i])
				{
					u[i]=1;
					tail++;
					tail=(tail-1)%50+1;
					que[tail]=i;
				}
			}
		}
	}while(head!=tail);
	for(int i=0;i<=n;i++)
	{
		ndis[x][i]=dis[i];
		if(i==x) continue;
		int w=i;
		while(pre[w]!=x)
		{
			w=pre[w];
			way[x][i][++way[x][i][0]]=w;
		}
		//way[x][i][++way[x][i][0]]=pre[w];
	}
	/*for(int i=0;i<=n;i++)
	{
		cout<<dis[i]<<" ";
	}
	cout<<endl;*/
}
int main()
{
	//freopen("a.txt","r",stdin);
	//freopen("b.txt","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			scanf("%d",&juz[i][j]);
		}
	}
	for(int i=0;i<=n;i++)
	{
		SPFA(i);
	}
	for(int i=1;i<=n;i++)
	u[i]=0;
	u[0]=1;
	DFS(0);
	printf("%d",ans);
	return 0;
}