AC

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll cnt = 0;

struct NODE {
	ll u, v, w;
	bool operator <(const NODE &other) const {
		return w < other.w;
	}
} edge[10010];
ll parent[10010];
ll rank_[10010];

int find(int x) {
	if (parent[x] != x) {
		parent[x] = find(parent[x]);
	}
	return parent[x];
}

void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)
		return;
	if (rank_[x] < rank_[y]) {
		parent[x] = y;
	} else {
		parent[y] = x;
		if (rank_[x] == rank_[y]) {
			rank_[x]++;
		}
	}
}

void kruskal(int n, int m) {

	sort(edge, edge + m);
	for (int i = 1; i <= n; i++) {
		parent[i] = i;
		rank_[i] = 0;
	}

	ll total = 0;
	int count = 0;

	for (int i = 0; i < m; i++) {
		int u = edge[i].u;
		int v = edge[i].v;
		ll w = edge[i].w;

		if (find(u) != find(v)) {
			unite(u, v);
			total += w;

		}
	}

	cout << total;

}

int main() {
	ll n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ll weight;
			cin >> weight;
			if (weight != 0 && j >= i + 1) {
				edge[cnt].u = i;
				edge[cnt].v = j;
				edge[cnt++].w = weight;
			}
		}
	}


	kruskal(n, cnt + 1);
	return 0;
}