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
#include<stdio.h>
#include<algorithm>
#define st first
#define nd second
using namespace std;
int par[2001];
pair<int,pair<int,int> >road[5000000];
int find(int x){
	if(par[x]==x)return x;
	par[x]=find(par[x]);
	return par[x];	
}
void link(int a,int b){
	par[find(a)]=find(b);	
}
main(){
	int n,m,nr=0;
	scanf("%d",&n);
	n++;
	m=n*(n-1)/2;
	for(int i=0;i<n;i++)par[i]=i;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			scanf("%d",&road[nr].st);
			road[nr++].nd=make_pair(i,j);
		}
	}
	sort(road,road+m);
	//for(int i=0;i<m;i++)cout<<road[i].st<<" "<<road[i].nd.st<<" "<<road[i].nd.nd<<"\n";
	long long wynik=0;
	for(int i=0;i<m;i++){
		if(find(road[i].nd.st)==find(road[i].nd.nd))continue;
		link(road[i].nd.st,road[i].nd.nd);
		wynik+=road[i].st;	
	}
	printf("%lld\n",wynik);
}