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
#include <bits/stdc++.h>
//#include <emmintrin.h>

using namespace std;

#define FORE(it,c)  for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
#define FOR(i,a,b)  for(int i=(a);i<(b);++i)
#define REP(i,a)    FOR(i,0,a)
#define ZERO(m)    memset(m,0,sizeof(m))
#define ALL(x)      x.begin(),x.end()
#define PB          push_back
#define S          size()
#define LL          long long
#define ULL        unsigned long long
#define LD          long double
#define MP          make_pair
#define X          first
#define Y          second
#define VC          vector
#define PII        pair <int, int>
#define VI          VC < int >
#define VVI        VC < VI >
#define VD          VC < double >
#define VVD        VC < VD >
#define VS          VC < string >
#define DB(a)      cerr << #a << ": " << (a) << endl;

template<class T> void print(VC < T > v) {cerr << "[";if (v.S) cerr << v[0];FOR(i, 1, v.S) cerr << ", " << v[i];cerr << "]\n";}
template<class T> string i2s(T x) {ostringstream o; o << x; return o.str(); }
VS splt(string s, char c = ' ') {VS all; int p = 0, np; while (np = s.find(c, p), np >= 0) {if (np != p) all.PB(s.substr(p, np - p)); p = np + 1;} if (p < s.S) all.PB(s.substr(p)); return all;}


PII p[2000 * 2000];
int g[2001];

int main() {
	int n;
	scanf("%d", &n);
	REP(i, n+1) g[i] = i;
	
	int pp = 0;
	REP(i, n) FOR(j, i+1, n+1) {
		scanf("%d", &p[pp].X);
		p[pp].Y = i * 2048 + j;
		pp++;
	}
	sort(p, p + pp);
	
	int pos = -1;
	int edges = 0;
	LL rv = 0;
	while (edges < n) {
		pos++;
		int a = p[pos].Y / 2048;
		int b = p[pos].Y & 2047;
		if (g[a] == g[b]) continue;
		
		int ga = g[a];
		int gb = g[b];
		REP(i, n + 1) if (g[i] == gb) g[i] = ga;
		
		rv += p[pos].X;
		edges++;
	}
	
	cout << rv << endl;
	return 0;
}