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
#include <cstdio>
#include <algorithm>

using namespace std;

int FU[ 2003 ];
int fu( int a )
{
    if ( FU[a]==a ) return a;
    return FU[a]=fu(FU[a]);
}

int fu_union( int a, int b )
{
    a=fu(a);
    b=fu(b);
    if ( a == b )
        return -1;
    FU[a]=b;
    return 0;
}

int S[ 2004*2004 ];
int W[ 2004*2004 ];

bool sort_func( int i, int j )
{ return W[i]<W[j]; }

int main()
{
    int n;
    scanf("%d",&n);
    
    for ( int i=0; i<=n; i++ ) FU[i]=i;
    int ils = 0;
    
    for ( int i=0; i<n; i++ )
        {
            for ( int j=i+1; j<=n; j++ )
                {
                    int kr_num = i*(n+1)+j;
                    scanf( "%d", W+kr_num );
                    //printf("%d %d %d\n",i,j,W[kr_num]);
                    S[ ils++ ] = kr_num;
                }
        }
    
    sort( S, S+ils, sort_func );
    
    long long wyn = 0;
    
    for ( int i=0; i<ils; i++ )
        {
            int s = S[i];
            if ( !fu_union(s%(n+1),s/(n+1)) )
                wyn += W[s];
        }
    
    printf("%lld\n",wyn);
    
    return 0;
}