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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<cstdio>
#include<algorithm>
#include<vector>
#include<iostream>
#include<cmath>

using namespace std;

typedef long long LL;

const int N = 2e3+77;

int c[N][N];
int n;
int p[N];

struct edge {
	int v,w,cost;
	edge(int a,int b,int c) {
		v = a, w = b, cost = c;
	}
};

vector<edge> worek;


bool operator < (edge a, edge b) {
	if(a.cost == b.cost) {
		if(a.v == b.v)
			return a.w < b.w;
		else
			return a.v < b.v;
	} else
		return a.cost < b.cost;
}

void wczytaj() {
	scanf("%d", &n);
	for(int i=1;i<=n;i++) 
		for(int j=i;j<=n;j++) {
			scanf("%d", &c[i][j+1]);
			worek.push_back(edge(i,j+1,c[i][j+1]));	
		}
	sort(worek.begin(), worek.end());
	n++;
	for(int i=1;i<=n;i++)
		p[i] = i;
}

int FIND(int v) {
	if(p[v] != v)	
		p[v] = FIND(p[v]);
	return p[v];
}

void UN(int v, int w) {
	v = FIND(v);
	w = FIND(w);
	if(v != w) p[v] = w;
}

LL jebaj() {
	LL res = 0;
	for(int i=0;i<(int)worek.size();i++)
		if (FIND(worek[i].v) != FIND(worek[i].w)) {
			UN(worek[i].v, worek[i].w);
			res += worek[i].cost;
		}
	return res;
}

int main () {
	wczytaj();
	printf("%lld", jebaj());
}