1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <cstdio>
#include <vector>
#include <algorithm>
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define REP(i,n) for(int i = 1; i <= (n); i++)
typedef long long LL;
using namespace std;
const int MAX = 2014;

struct Edge {
	int u,v; // u <= v
	int c;
	Edge(){}
	Edge(int u, int v, int c): u(u), v(v), c(c){}
};
bool cmd(const Edge &a, const Edge &b) {
	return a.c < b.c;
}

int n;
vector<Edge> E;
int R[MAX], P[MAX];

int get_par(int x) {
	if(x == P[x]) return x;
	P[x] = get_par(P[x]);
	return P[x];
}

void link(int a, int b) {
	a = get_par(a);
	b = get_par(b);
	if(R[a] == R[b]) R[a] ++;
	if(R[a] < R[b]) swap(a,b);
	P[b] = a;
}

int main() {
	int c;
	long long ans = 0;
	scanf("%d", &n);
	REP(i,n) {
		for(int j = i; j <= n; j++) {
			scanf("%d", &c);
			E.push_back(Edge(i - 1,j,c));
		}
	}
	sort(E.begin(), E.end(), cmd);
	FOR(i,n+1) P[i] = i;
	for(auto e: E) {
		if(get_par(e.u) == get_par(e.v))
			continue;
		link(e.u, e.v);
		ans += (LL)e.c;
	}
	printf("%lld\n", ans);
}