#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
 
using namespace std;
 
typedef struct tagNode {
	int id, value;
	tagNode(const int& a, const int& b) : id(a), value(b) {}
	bool operator < (const tagNode& x) const {
		return value > x.value;
	}
} Node;
 
const int MAXN = 1510;
const int INF = 0x7fffffff;
int G[MAXN][MAXN];
int n = 0;
 
int QuickRead() {
	int zf = 1, ret = 0;
	char ch = getchar();
	while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
	if (ch == '-') zf = -1;
	else ret = ch - '0';
	ch = getchar();
	while (ch >= '0' && ch <= '9') {
		ret = ret * 10 + ch - '0';
		ch = getchar();
	}
	return ret*zf;
}
 
void Init() {
	n = QuickRead();
	//scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			G[i][j] = QuickRead();
			//scanf("%d", G[i]+j);
			if (G[i][j] < 0) G[i][j] = INF;
		}
	}
}
 
int MST_Prim() {
	int total = 0;
	bool used[MAXN];
	int lowcost[MAXN];
	
	memset(used, false, sizeof(used));
	used[1] = true;
	for (int i = 2; i <= n; ++i) {
		lowcost[i] = G[1][i];
	}
	
	int k = 0, id = 0, cnt = 1, min = INF;
	while (cnt < n) {
		// 找lowcost最小的
		k = 1;
		min = INF;
		for (int i = 2; i <= n; ++i) {
			if (!used[i] && min > lowcost[i]) {
				min = lowcost[i];
				k = i;
			}
		}
		total += min;
		used[k] = true;
		++cnt;
		
		// 更新lowcost
		for (int i = 2; i <= n; ++i) {
			if (!used[i] && lowcost[i] > G[k][i]) {
				lowcost[i] = G[k][i];
			}
		}
	}
	return total;
}
 
int main() {
	freopen("mcst.in", "r", stdin);
	freopen("mcst.out", "w", stdout);
	
	Init();
	int ans = MST_Prim();
	printf("%d", ans);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}