#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1505;
int n,mst=0,minn,a[maxn][maxn],lowcost[maxn];
bool vis[maxn]={0};

void Prim(){
	for(int i=1;i<=n;i++)lowcost[i]=a[1][i];
	vis[1]=1;
	for(int i=2;i<=n;i++){
		int j=0;minn=0x7fffffff;
		for(int k=2;k<=n;k++){
			if(!vis[k] && minn>lowcost[k]){
				minn=lowcost[k];j=k;
			}
		}
		vis[j]=1;mst+=minn;
		for(int k=2;k<=n;k++)
			if(!vis[k] && a[j][k]<lowcost[k])
				lowcost[k]=a[j][k];
	}
	printf("%d\n",mst);
	return;
}

int main()
{
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	memset(a,0x7f,sizeof a);
	scanf("%d",&n);int x;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%d",&x);
			if(x!=-1)a[i][j]=x;
		}
	}
	Prim();
	return 0;
}