#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1510;
int dis[maxn][maxn];
int n;
int prim();
void Find(int);
void hebing(int,int);
int main()
{
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int x;
			scanf("%d",&x);
			if(x==-1)
			{
				dis[i][j]=0x7fffff;
			}
			else dis[i][j]=x;
		}
	}
	int k=prim();
	printf("%d",k);
}
int prim()
{
	int i,j,k,min,mst=0,lowcost[maxn],closeset[maxn];bool used[maxn]={0};
	for(int i=1;i<=n;i++)
	{
		lowcost[i]=dis[1][i];
		closeset[i]=1;
	}
	used[1]=1;
	for(int i=1;i<=n-1;i++)
	{
		j=0;min=0x7fffffff;
		for(k=1;k<=n;k++)
		{
			if(!used[k]&&(lowcost[k]<min))
			{
				min=lowcost[k],j=k;
			}
		}
			used[j]=1;
			mst+=min;
			for(k=1;k<=n;k++)
			{
				if(!used[k]&&(dis[j][k]<lowcost[k]))
				{
					lowcost[k]=dis[j][k];
					closeset[k]=j;
				}
			}
		
	}
	return mst;
}