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
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include <unistd.h>
using namespace std;
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
typedef long long LL;
const int INF = 2000000000;

class Input {
 public:
  Input() { bufpos = bufend = buffer; eof = false; }
  bool Eof() { return eof; }
  char Peek() { if(bufpos == bufend) Grab(); return *bufpos; }
  unsigned char UPeek() { return static_cast<unsigned char>(Peek()); }
  void SkipWS();
  template<class T> T Get();
  void operator()() {}
  template<class Arg, class... Args> void operator()(Arg &arg, Args &... args) {
    arg = Get<Arg>();
    operator()(args...);
  }
 private:
  static const int BUFSIZE = 1<<16;
  char buffer[BUFSIZE];
  char *bufpos;
  char *bufend;
  bool eof;
  void Grab();
};

void Input::Grab() {
  if(eof) return;
  bufpos = buffer;
  bufend = buffer + read(0, buffer, BUFSIZE);
  if(bufend==bufpos) { eof=true; *bufpos=0; }
}

template<> inline char Input::Get<char>() {
  char res = Peek();
  ++bufpos;
  return res;
}

void Input::SkipWS() {
  while(isspace(UPeek())) Get<char>();
}

template<> unsigned Input::Get<unsigned>() {
  SkipWS();
  unsigned x = 0;
  while(isdigit(UPeek())) {
    x = 10u * x + (Get<char>()-'0');
  }
  return x;
}

template<> int Input::Get<int>() {
  unsigned x = Get<unsigned>();
  return static_cast<int>(x);
}

Input IN;


const int MAXV = 2001;

int V;
int EDGE[MAXV][MAXV];

void ReadInput() {
  IN(V); ++V;
  REP(a,V) for(int b=a+1;b<V;++b) IN(EDGE[a][b]);
}

void Transpose() {
  REP(a,V) REP(b,a) EDGE[a][b] = EDGE[b][a];
}

LL MST() {
  vector<int> dist(V,INF);
  vector<char> done(V,0);
  dist[0]=0;
  LL res = 0;
  for(;;) {
    int x=-1, bestDist = INF;
    REP(i,V) if(!done[i] && dist[i]<bestDist) { x=i; bestDist=dist[i]; }
    if(x==-1) break;
    res += bestDist;
    done[x] = 1;
    REP(y,V) if(!done[y]) dist[y] = min(dist[y], EDGE[x][y]);
  }
  return res;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(nullptr);
  ReadInput();
  Transpose();
  LL res = MST();
  cout << res << '\n';
}