#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#define MAXN 110
#define INF 0x3f3f3f3f
using namespace std;
struct Edge
{
	int v,dist;
	Edge(int vv,int dd):v(vv),dist(dd){};
	bool operator < (const Edge e) const
	{
		return dist>e.dist;
	}
};

vector<Edge> edge[MAXN];

int Prim (int n)
{
	Edge temp(0,0);
	int dist[MAXN];
        int visited[MAXN];
	priority_queue<Edge> q;
	int done=0;
	int sum=0;
	for(int i=0;i!=n;++i)
	{
		dist[i]=INF;
		visited[i]=0;
	}
	q.push(temp);
	while(done<n && !q.empty())
	{
		do
		{
			temp=q.top();
			q.pop();
		}while(visited[temp.v]==1 && !q.empty());
		if(visited[temp.v]==0)
		{
			sum+=temp.dist;
			visited[temp.v]=1;
			++done;
			for(int i=0;i!=edge[temp.v].size();++i)
			{
				int k=edge[temp.v][i].v;
				if(visited[k]==0)
				{
					int w=edge[temp.v][i].dist;
					if(dist[temp.v]>w)
					{
						dist[temp.v]=w;
						q.push(Edge(k,w));
					}
					
				}
			}
		}
	}
	if(done<n)
	return -1;
	return sum;
}

int main()
{
	int n,w;
	while(scanf("%d",&n)!=EOF &&n)
	{
		for(int i=0;i!=n;++i)
		edge[i].clear();
		for(int i=0;i!=n;++i)
		for(int j=0;j!=n;++j)
		{
			scanf("%d",&w);
			edge[i].push_back(Edge(j,w));
		 }
		 printf("%d\n",Prim(n));
	}
	return 0;
}