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



#define NODE_NUM 100
#define MAX_VALUE 10000000

int weight[NODE_NUM][NODE_NUM];
int visited[NODE_NUM];
int low_cost[NODE_NUM];
int prececessor[NODE_NUM];


/*
 * ??°??????????????????vertex_idx???????§??????¨?????????????°???¨?????¨????±?????????¢??°
 * ??°?????????????????????????????°???vertex_num
 * ??£??\??????weight?????\?????¨??????????°???¨?????¨????§??????????
 * ??????prececessor??????????????????????????£??\????????????idx???????´??????????
 */
void Prim(int vertex_idx, int vertex_num){
    
    int i, j;
    
    /*
     * min???,?????¢????§???????????????¨?????¨??????????°???????????????§????????????????¬????????????????????????¢/????????????
     * k???,?????¢????§???????????????¨?????¨??????????°???????????????§????????????????¬????????????????idx??????????????????????´???????
     */
    int k, min;
    
    /*
     * ?????????vertex_idx???????§????????????§???????????????????????°??????????????????
     */
    visited[vertex_idx] = 1;
    
    /*
     * ????????????????§??????????vertex_idx????????°???????????????????????????????????¢/?????????low_cost?????????????´???????
     */
    for (i = 0; i < vertex_num ; i++) {
        low_cost[i] = weight[vertex_idx][i];
    }
    
    /*
     * prececessor???????????????????°???¨?????¨????§???????????????´??????????????????????????????????????\????????????idx???????´??????????
     * ???????????¨?????????vertex_idx???????´???????
     */
    for (i = 0; i < vertex_num ; i++) {
        prececessor[i] = vertex_idx;
    }
    
    
    for (i = 1; i< vertex_num; i++) {
        min = low_cost[vertex_idx];
        k = vertex_idx;
        
        /*
         * min???,?????¢????§???????????????¨?????¨??????????°???????????????§????????????????¬????????????????????????¢/????????????
         * k???,?????¢????§???????????????¨?????¨??????????°???????????????§????????????????¬????????????????idx??????????????????????´???????
         */
        for (j = 0; j < vertex_num; j++) {
            if (!visited[j] && min > low_cost[j]) {
                min = low_cost[j];
                k = j;
            }
        }
        
        /*
         * ?????????k??????????¬??????¨?????¨?????????????????????????????????????????????????????°??????????????????
         */
        visited[k] = 1;
    
        /*
         * ??°??????????????????????????????k??????????????¢/??????????????£??????low_cost???????????´??°???????????´???????????´??°?????????
         * ??????????????????prececessor???????????´??°?????????
         */
        for (j = 1; j < vertex_num; j++) {
            if (!visited[j]  && low_cost[j] > weight[k][j]) {
                low_cost[j] = weight[k][j];
                prececessor[j] = k;
            }
        }
    }
}


int main( ){
    
    int i, j, v, n;
    int ans = 0;
    
    scanf("%d", &n);
    
    for (i=0; i<n; i++){
        for (j = 0; j < n; j++) {
            scanf("%d", &v);
            if (v == -1) {
                weight[i][j] = MAX_VALUE;
            }else{
                weight[i][j] = v;
            }
        }
    }
    
    Prim(0, n);
    
    for (i=1; i<n; i++) {
        ans += weight[i][prececessor[i]];
    }
    
    printf("%d\n", ans);
    
    
    return 0;
}

Measured memory_bytes: 636