#include<bits/stdc++.h> using namespace std; const int N=114514; struct edge{ int a,b,w; }e[N*N]; int n; int k; int p[N]; int ans; bool cmp(edge e1,edge e2){ return e1.w<e2.w; } int find(int x){ if(p[x]!=x) return p[x]=find(p[x]); return p[x]; } int kru(){ int cnt=0; sort(e+1,e+k+1,cmp); for(int i=1;i<=n;i++) p[i]=i; for(int i=1;i<=k;i++){ if(cnt==n-1) break; int fa=find(e[i].a),fb=find(e[i].b); if(fa!=fb){ p[fb]=fa; ans+=e[i].w; cnt++; } } if(cnt<n-1) return false; return ans; } int main(){ cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ int t; cin>>t; if(t!=0){ k++,e[k]={i,j,t}; } } } cout<<kru(); return 0; }