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
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
using namespace std;
typedef pair<int,int> PI;
typedef long long LL;
typedef double D;
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define R(I,N) for(int I=0;I<N;I++)
#define F(I,A,B) for(int I=A;I<B;I++)
#define FD(I,N) for(int I=N-1;I>=0;I--)
#define make(A) scanf("%d",&A)
#define MAX 2010
struct prze{
	int a,b,c;
};
vector<prze> t;
bool q(prze a,prze b){
	return a.c < b.c;
}
int f[MAX];
int find(int a){
	return a==f[a]?a:f[a]=find(f[a]);
}
bool uni(int a,int b){
	a = find(a);
	b = find(b);
	if(a==b)return 0;
	f[a]=b;
	return 1;
}
main(){
	int n;make(n);
	R(i,n+1){
		f[i] = i;
		F(j,i+1,n+1){
			int pom;make(pom);
			prze ak = {a:i,b:j,c:pom};
			t.PB(ak);
		}
	}
	sort(t.begin(),t.end(),q);
	LL wyn = 0;
	R(i,t.size())if(uni(t[i].a,t[i].b))wyn+=t[i].c;
	printf("%lld\n",wyn);
}