#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>


/*
 * ????????????????????\??????????£??????\???????????????
 * ????????§??????max??????????§?????????¨??????????£?????????????????????????????????£???????????????????????\??§??¨?????????????????????
 */
#define ELEMENT_NUM 1000000

typedef struct EDGE{
    int frm;
    int to;
    int weight;
}EDGE;

typedef struct UF{
    int parent;
}UF;


EDGE heap[ELEMENT_NUM + 1];
UF uf[ELEMENT_NUM + 1];
int last_idx;


void initialize(int num){
    int i ;
    
    for (i=1; i <= num; i++) {
        uf[i].parent = i;
    }
}

int find(int a){

    if (a == uf[a].parent) {
        return a;
    }
    
    return uf[a].parent = find(uf[a].parent);
}

int isSame(int a, int b){
    
    if (find(a) == find(b)) {
        return 1;
    }
    else{
        return 0;
    }
}

void unite(int a, int b){
   a = find(a);
   b = find(b);
    
    if (a == b) {
        return;
    }
    
    uf[b].parent = a;
    
}



/*
 * heap????????????????´?node_idx?????????????????????????´?????????¨?????????????????????heap?????????????????§?°???¢???????????????????????????????´????????§??????????
 */
void maxHeapify(int node_idx){
    
    EDGE tmp;
    int largest = node_idx;
    int left_child_idx = 2 * node_idx;
    int right_child_idx = 2 * node_idx + 1;
    
    
    if ( left_child_idx <= last_idx && heap[left_child_idx].weight > heap[node_idx].weight) {
        largest = left_child_idx;
    }else{
        largest = node_idx;
    }
    if ( right_child_idx <= last_idx && heap[right_child_idx].weight > heap[largest].weight) {
        largest = right_child_idx;
    }
    
    if (largest != node_idx) {
        tmp = heap[largest];
        heap[largest] = heap[node_idx];
        heap[node_idx] = tmp;
        
        maxHeapify(largest);
    }
}

/* heap????????????????´?????????????????????¨?????§?°???¢???????????????????????????????°?????????´?????????????´???????????????????
 * ??§?°???¢???????????¶????????????????????????????????????????????§??°???????????????????????????
 */
void heapIncreaseKey(int key){
    
    int i = last_idx;
    EDGE tmp;
    
    while( i > 1 && heap[i/2].weight < heap[i].weight){
        tmp = heap[i];
        heap[i] = heap[i/2];
        heap[i/2] = tmp;
        i = i/2;
    }
    
}

/*
 * ??????????????\??????heap)???????´????????????????
 */
void enqueue(int key, int frm, int to){
    last_idx++;
    heap[last_idx].weight = key;
    heap[last_idx].frm = frm;
    heap[last_idx].to = to;
    heapIncreaseKey(key);
}

/*
 * ??????????????\??????heap)??????????´???????????????????
 */
EDGE dequeue(){
    
    EDGE tmp = heap[1];
    heap[1] = heap[last_idx--];
    
    /* ??????????´???????????????????????????£????????????heap???????§?????????? */
    maxHeapify(1);
    return tmp;
}


int isEmpty(){
    if (last_idx == 0) {
        return 0;
    }
    else{
        return 1;
    }
}


int Kruskal(int n){
    EDGE A;
    int ans = 0;
    int tmp;
    
    initialize(n);
    
    while ( isEmpty() ) {
        A = dequeue();
        if ( !isSame(A.frm, A.to) ){
            unite(A.frm, A.to);
            tmp = ~(A.weight);
            ans += tmp;
        }
    }
    
    return ans;
}


int main( ){
    
    int i, j, c, n;
    
    scanf("%d", &n);
    
    for (i=1; i<=n; i++){
        
        for (j = 1; j <= n; j++) {
            scanf("%d", &c);
            if (c != -1) {
                enqueue(~c, i, j);
            }
        }
    }
    
    printf("%d\n", Kruskal(n));
    
    return 0;
}

Measured memory_bytes: 2652