#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back using namespace std; inline int read(){ int x=0; short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,G[20][20],dfn[20],low[20],stk[20],instk[20],top,cnt,res=2e9; vector<int>v[20]; int tot,tim; void dfs(int u){ dfn[u]=low[u]=++cnt; stk[++top]=u,instk[u]=1; for(int x:v[u]){ if(!dfn[x]){ dfs(x);low[u]=min(low[u],low[x]); }else if(instk[x])low[u]=min(low[u],dfn[x]); }if(dfn[u]==low[u]){ ++tot; while(top){ int x=stk[top--]; instk[x]=0; if(x==u)break; } } } bool chk(){ top=0; up(i,1,n)dfn[i]=low[i]=instk[i]=0; cnt=0,tot=0; up(i,1,n)if(!dfn[i]){ dfs(i); if(tot>=2)return 0; }return 1; } void DFS(int x,int y,int c){ ++tim; if(c>=res)return; if(y>n)x++,y=x+1; if(tim>=3e8){ if(res==int(2e9))cout<<"-1\n"; else cout<<res<<'\n'; //cout<<clock()*1.0/CLOCKS_PER_SEC<<"s\n"; exit(0); } if(x>n){ if(chk())res=min(res,c);return; }if(G[x][y]==-1){ DFS(x,y+1,c); return; } if(G[x][y]<G[y][x]){ v[x].p_b(y);DFS(x,y+1,c+G[x][y]);v[x].pop_back(); v[y].p_b(x);DFS(x,y+1,c+G[y][x]);v[y].pop_back(); }else { v[y].p_b(x);DFS(x,y+1,c+G[y][x]);v[y].pop_back(); v[x].p_b(y);DFS(x,y+1,c+G[x][y]);v[x].pop_back(); } } void slv(){ n=read(); up(i,1,n)up(j,1,n)G[i][j]=read(); DFS(1,1,0); if(res==int(2e9))cout<<"-1\n"; else cout<<res<<'\n'; } int main(){ // freopen("anatomy.in","r",stdin); // freopen("anatomy.out","w",stdout); slv(); // fclose(stdin); // fclose(stdout); return 0; }