#include<bits/stdc++.h>
using namespace std;
enum{N=18,M=262149};
int e[N][N],f[M][N][N],ans[M];
int main(){ios::sync_with_stdio(0);cin.tie(0);
	int n,o,i,j,k,l,u,v,w,x,sum=0;
	cin>>n,o=1<<n;
	for(i=0;i<n;++i)for(j=0;j<n;++j)cin>>e[i][j];
	for(i=0;i<n;++i)for(j=0;j<=i;++j)if(e[i][j]==-1)e[i][j]=e[j][i]=1e9;
	else k=min(e[i][j],e[j][i]),sum+=k,e[i][j]-=k,e[j][i]-=k;
	memset(f,63,sizeof f),memset(ans,63,sizeof ans),ans[1]=0;
	for(i=1;i<o;i+=2){
		/*for(j=0;j<n;++j)if(i>>j&1)for(l=0;l<n;++l)if(i>>l&1)f[i][l][l]=min(f[i][l][l],f[i][j][l]+e[j][l]);
		for(j=0,k=1e9;j<n;++j)k=min(k,f[i][j][j]);*/
		k=ans[i];
		//cout<<i<<' '<<k<<'!'<<'\n';
		for(j=0;j<n;++j)if(i>>j&1)for(l=0;l<n;++l)if(i>>l&1){
			u=f[i][j][l];
			if(j!=l)u=min(u,k);
			if(u<6e8)for(v=0;v<n;++v)if(!(i>>v&1)){if(x=u+e[j][v],x<6e8)w=i|(1<<v),
			f[w][v][l]=min(f[w][v][l],x),ans[w]=min(ans[w],x+e[v][l]);}
			if(j==l){
				u=k;
				if(u<6e8)for(v=0;v<n;++v)if(!(i>>v&1))f[i|(1<<v)][v][l]=min(f[i|(1<<v)][v][l],u+e[j][v]);
			}
		}
	}
	if(k<6e8)cout<<sum+k;else cout<<-1;
}