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
#define debug if(1)
// Grzegorz Guspiel
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i,n) for(int i=0;i<int(n);++i)
#define SIZE(c) ((int)((c).size()))
#define FOREACH(i,x) for (__typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second

template<typename T> void maxE(T& a, const T& b) { a = max(a, b); }
template<typename T> void minE(T& a, const T& b) { a = min(a, b); }

const int MAXN = 2 * 1000 + 10;

struct Offer {
    int i, j;
    int cost;
};
bool operator<(const Offer& a, const Offer& b) { return a.cost < b.cost; }

int n;
vector<Offer> offers;
int p[MAXN];

int fs(int a) {
    if (p[a] != p[p[a]]) p[a] = fs(p[a]);
    return p[a];
}
void us(int a, int b) {
    a = fs(a);
    b = fs(b);
    if (rand() % 2) swap(a, b);
    p[a] = b;
}

int main() {
    scanf("%d", &n);
    offers.clear();
    Offer offer;
    for (offer.i = 1; offer.i <= n; offer.i++) {
        for (offer.j = offer.i; offer.j <= n; offer.j++) {
            scanf("%d", &offer.cost);
            offers.pb(offer);
        }
    }

    sort(ALL(offers));
    int m = n + 3;
    REP (i, m) p[i] = i;
    long long result = 0;

    FOREACH (offer, offers) {
        int i = offer->i;
        int j = offer->j + 1;
        if (fs(i) == fs(j)) continue;
        us(i, j);
        result += offer->cost;
    }

    printf("%lld\n", result);
	return 0;
}