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
76
77
78
#include <iostream>
#include <list>
#include <vector>
#include <algorithm>

using namespace std;

struct glink
{
	int a;
	int b;
	long long unsigned value;
	glink(int a, int b, long long unsigned value){ this->a = a; this->b = b; this->value=value; }
};

bool compare(glink i, glink j) { return i.value < j.value; }

list<glink> links;
vector<int> colors(2001,0);
int colorCounter=1, n;

bool add(int a, int b)
{
	if ((colors[a]) && (colors[a]==colors[b]))
		return false;
	if (!colors[a] && !colors[b])
	{
		colors[a]=colors[b]=colorCounter++;
		return true;
	}
	if (!colors[a])
	{
		colors[a]=colors[b];
		return true;
	}
	if (!colors[b])
	{
		colors[b]=colors[a];
		return true;
	}
	for (int i=0; i<=n; i++)
		if (colors[i]==colors[b]) colors[i]=colors[a];
	return true;
}

int main()
{
	long long unsigned price=0, p;
	int m, k;
	cin >> n;
	
	k=n;
	while(k)
	{
		m=k--;
		while (m--)
		{
			cin >> p;
			links.push_back(glink(n-k-1, n-m, p));
		}
	}
	
	links.sort(compare);
	auto element = links.begin();
	
	k=n;
	while (k)
	{
		if (add(element->a, element->b))
		{
			k--;
			price+=element->value;
		}
		element++;
	}
	cout << price << endl;
	return 0;
}