#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int Prim(int);
int const maxn=1505;
int n,G[maxn][maxn],m;
int main()
{
	freopen("mcst.in","r",stdin);
	freopen("mcst.out","w",stdout);
	memset(G,0x7f,sizeof(G));
	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)G[i][j]=x;
	}
	int k=Prim(n);
	if(k==0x7f7f7f7f)	printf("-1");
	else printf("%d",k);
}
int Prim(int v) 
{
	int i,j,k,min,mst=0,lowcost[maxn],used[maxn];
	for(i=1;i<=v;i++)
	{
		lowcost[i]=G[1][i];
		used[i]=0;
	}
	used[1]=1;
	for(i=1;i<v;i++)
	{
		j=0;min=0x7fffffff; 
		for(k=1;k<=v;k++)
		if(!used[k]&&lowcost[k]<min)
		{
			min=lowcost[k];j=k;
		}
		used[j]=1;
		mst+=min;
		for(k=1;k<=v;k++)
		{
			if(!used[k]&&(G[j][k]<lowcost[k]))
			{
			lowcost[k]=G[j][k];
			}
		}
	}
	return mst;
}