#include <bits/stdc++.h> using namespace std; #define ll long long #pragma optimize(2) const int maxn=1010; int n; ll a[maxn][maxn]; vector<int> edge[maxn]; struct node { int u,v,x; }f[maxn]; int tot; bool vis[maxn]; int dfn[maxn],low[maxn],cnt; int s[maxn],top,scc; void chkdfs(int u) { dfn[u]=low[u]=++cnt; s[++top]=u; for(int i=0;i<edge[u].size();i++) { int v=edge[u][i]; if(!dfn[v]) { chkdfs(v); low[u]=min(low[u],low[v]); } else low[u]=min(low[u],dfn[v]); } if(dfn[u]==low[u]) { while(top) { int t=s[top]; top--; if(t==u) break; } scc++; } } bool chk() { cnt=top=scc=0; for(register int i=1;i<=n;i++) dfn[i]=low[i]=0; chkdfs(1); if(scc!=1) return 0; return 1; } ll ans=1e15; ll cut; inline void dfs(int p,ll sum) { if(sum>ans) return ; if(p>tot) { for(register int i=1;i<=n;i++) edge[i].clear(); for(register int i=1;i<=tot;i++) { int u=f[i].u,v=f[i].v; if(f[i].x==1) swap(u,v); edge[u].push_back(v); } if(chk()) ans=sum; return ; } int u=f[p].u,v=f[p].v; f[p].x=1; dfs(p+1,sum+a[v][u]); f[p].x=0; dfs(p+1,sum+a[u][v]); } void sol() { dfs(1,0); } signed main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) cin>>a[i][j]; for(int i=1;i<=n;i++) { for(int j=i+1;j<=n;j++) { if(a[i][j]==-1) continue; f[++tot]={i,j,0}; } } if(tot<=50) { sol(); if(ans>1e12) cout<<-1<<endl; else cout<<ans<<endl; return 0; } cout<<-1<<endl; return 0; }