kruskal

#include <stdio.h>

int adapted_partition(long int* weights, long int* u, long int* v, long int begin, long int end){
	long int pivot, top, i, aux_u, aux_v;
	pivot = weights[begin];
	aux_u = u[begin];
  aux_v = v[begin];

  top = begin;
	for(i = begin + 1; i <= end; i++){
		if(weights[i] < pivot){
			weights[top] = weights[i];
			weights[i] = weights[top + 1];

      u[top] = u[i];
      u[i] = u[top + 1];

      v[top] = v[i];
      v[i] = v[top + 1];

			top++;
		}
	}

	weights[top] = pivot;
  u[top] = aux_u;
  v[top] = aux_v;

	return top;
}

void adapted_quicksort(long int* weights, long int* u, long int* v, long int begin, long int end){ //Best case: O(n*logn) - Worst case: O(n²)
	long int middle;
	if(begin < end){
		middle = adapted_partition(weights, u, v, begin, end);
		adapted_quicksort(weights, u, v, begin, middle - 1);
		adapted_quicksort(weights, u, v, middle + 1, end);
	}
}


void kruskal(long int n, long int graph[n][n]){
  long int trees[n][n];
  long int trees_size[n];
  long int trees_index[n];
  long int trees_u[n][n];
  long int trees_v[n][n];
  long int trees_w[n][n];

  long int num_valid_vertexs = 0;
  for(long int i = 0; i < n; i++){
    trees[i][0] = i;
    trees_index[i] = i;
    trees_size[i] = 1;

    for(long int j = i+1; j < n; j++){
      if(graph[i][j] != 0){
        num_valid_vertexs+= 1;
      }
    }
  }

  long int u[num_valid_vertexs], v[num_valid_vertexs], w[num_valid_vertexs];
  long int count = 0;
  for(long int i = 0; i < n; i++){
    for(long int j = i+1; j < n; j++){
      if(graph[i][j] != 0){
        u[count] = i;
        v[count] = j;
        w[count] = graph[i][j];
        count += 1;
      }
    }
  }

  adapted_quicksort(w, u, v, 0, count - 1);

  //printf("sorted weights: \n");
  //for(long int i = 0; i < count; i++){
  //  printf("u: %ld - v: %ld - weight: %ld\n", u[i], v[i], w[i]);
  //}

  for(long int i = 0; i < count; i++){
    //printf("trees indexes: \n");
    //for(long int k = 0; k < n; k++){
    //  printf("tree id: %ld - parent: %ld\n", k, trees_index[k]);
    //}

    if(trees_index[u[i]] != trees_index[v[i]]){
      //printf("u: %ld - v: %ld - weight: %ld\n", u[i], v[i], w[i]);
      //printf("mixing tree %ld with tree %ld\n", trees_index[u[i]], trees_index[ v[i] ]);

      //printf("before: \n");
      //printf("tree %ld (size: %ld): \n", trees_index[u[i]], trees_size[trees_index[u[i]]]);
      //for(int k = 0; k < trees_size[trees_index[u[i]]]; k++){
      //  printf("%ld ", trees[trees_index[u[i]]][k]);
      //}
      //printf("\n");

      //printf("tree %ld: (size: %ld)\n", trees_index[v[i]], trees_size[trees_index[v[i]]]);
      //for(int k = 0; k < trees_size[trees_index[v[i]]]; k++){
      //  printf("%ld ", trees[trees_index[v[i]]][k]);
      //}
      //printf("\n\n");

      long int j = 0;
      long int old_size_first_tree = trees_size[ trees_index[ u[i] ] ];
      long int old_size_second_tree = trees_size[ trees_index[ v[i] ] ];

      while(j < trees_size[ trees_index[ v[i] ] ]){
        //printf("add %ld to tree %ld\n", trees[trees_index[v[i]]][j], trees_index[ u[i] ]);
        trees[ trees_index[ u[i] ] ][ trees_size[trees_index[u[i]]] ] = trees[trees_index[v[i]]][j];

        trees_size[ trees_index[ u[i] ] ] += 1;
        j++;
      }

      // trees with only one vertex
      if(old_size_first_tree == 1 && old_size_second_tree == 1){
        trees_u[ trees_index[ u[i] ] ][0] = u[i];
        trees_v[ trees_index[ u[i] ] ][0] = v[i];
        trees_w[ trees_index[ u[i] ] ][0] = w[i];

      }else{
        for(long int k = 0; k < (old_size_second_tree - 1); k++){
          trees_u[ trees_index[ u[i] ] ][old_size_first_tree - 1] = trees_u[ trees_index[ v[i] ] ][k];

          trees_v[ trees_index[ u[i] ] ][old_size_first_tree - 1] = trees_v[ trees_index[ v[i] ] ][k];

          trees_w[ trees_index[ u[i] ] ][old_size_first_tree - 1] = trees_w[ trees_index[ v[i] ] ][k];

          old_size_first_tree += 1;
        }

        trees_u[ trees_index[ u[i] ] ][old_size_first_tree - 1] = u[i];
        trees_v[ trees_index[ u[i] ] ][old_size_first_tree - 1] = v[i];
        trees_w[ trees_index[ u[i] ] ][old_size_first_tree - 1] = w[i];
      }

      //printf("vertexes: \n");
      //for(long int k = 0; k < trees_size[ trees_index[ u[i] ] ] - 1; k++){
      //  printf("u: %ld - v: %ld - w: %ld\n", trees_u[trees_index[ u[i] ]][k], trees_v[trees_index[ u[i] ]][k], trees_w[trees_index[ u[i] ]][k]);
      //}
      //printf("\n");

      //printf("trees indexes: \n");
      long int old_index = trees_index[v[i]];
      for(long int k = 0; k < n; k++){
        if(trees_index[k] == old_index){
          trees_index[k] = trees_index[u[i]];
        }
        //printf("tree id: %ld - parent: %ld\n", k, trees_index[k]);
      }

      //printf("after: \n");
      //printf("tree %ld (size: %ld): \n", trees_index[u[i]], trees_size[trees_index[u[i]]]);
      //for(int k = 0; k < trees_size[trees_index[u[i]]]; k++){
      //  printf("%ld ", trees[trees_index[u[i]]][k]);
      //}
      //printf("\n");

    }
  }

  /* uncomment to see the minimal spanning tree
  printf("---- minimal spanning tree ----\n");
  for(long int i = 0; i < trees_size[ trees_index[0] ] - 1; i++){
    printf("u: %ld - w: %ld - w: %ld\n", trees_u[trees_index[0]][i], trees_v[trees_index[0]][i], trees_w[trees_index[0]][i]);
    total += trees_w[trees_index[0]][i];
  }
  printf("\n")
  */

  long int total = 0;
  for(long int i = 0; i < trees_size[ trees_index[0] ] - 1; i++){
    total += trees_w[trees_index[0]][i];
  }
  printf("%ld\n", total);
}

int main(void) {
  long int n;

  scanf("%ld", &n);

  long int graph[n][n];
  long int weight;

  for(long int i = 0; i < n-1; i++){
    for(long int j = 0; j < n - 1 - i; j++){
      scanf("%ld", &weight);
      graph[i][j+i+1] = weight;
      graph[i+j+1][i] = weight;
    }
    graph[i][i] = 0;
  }
  graph[n-1][n-1] = 0;

  kruskal(n, graph);
}