#include <bits/stdc++.h> #define LL long long #define PII pair<int,int> #define ULL unsigned long long using namespace std; int N,M; PII pi[150]; int a[20][20]; int ans=1e9; vector<int>gra[20]; bool vis[20]; int cnt=0; void dfs2(int u) { cnt++; vis[u]=1; for(int i=0;i<gra[u].size();i++) { int v=gra[u][i]; if(!vis[v]) dfs2(v); } return; } bool flag=0; void dfs(int p,int tot) { if(flag) return; if(ans<=tot) return; if(p==M) { if(1.0*clock()/CLOCKS_PER_SEC>2.99) flag=1; for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) vis[j]=0; cnt=0; dfs2(i); if(cnt!=N) return; } ans=min(ans,tot); return; } int x=pi[p+1].first,y=pi[p+1].second; if(a[x][y]<a[y][x]) { gra[x].push_back(y); dfs(p+1,tot+a[x][y]); gra[x].pop_back(); gra[y].push_back(x); dfs(p+1,tot+a[y][x]); gra[y].pop_back(); } else { gra[y].push_back(x); dfs(p+1,tot+a[y][x]); gra[y].pop_back(); gra[x].push_back(y); dfs(p+1,tot+a[x][y]); gra[x].pop_back(); } return; } int main() { //freopen("anatomy.in","r",stdin); //freopen("anatomy.out","w",stdout); scanf("%d",&N); for(int i=1;i<=N;i++) { for(int j=1;j<=N;j++) { scanf("%d",&a[i][j]); } } for(int i=1;i<=N;i++) { for(int j=i+1;j<=N;j++) { if(a[i][j]>=0) pi[++M]={i,j}; } } // printf("%d\n",M); dfs(0,0); if(ans==1e9) ans=-1; printf("%d\n",ans); return 0; }