Go: package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)

	g := make([][]int, n)
	ans := make([][]int, n)

	inf := 1 << 30
	for i := 0; i < n; i++ {
		g[i] = make([]int, n)
		ans[i] = make([]int, n)
		for ii := 0; ii < n; ii++ {
			g[i][ii] = getNextInt(scanner)
			if g[i][ii] == -1 {
				g[i][ii] = inf
			}
			ans[i][ii] = -1
		}
	}

	im := make(IntMap, 1)

	im.increment(1)

	for len(im) < n {
		min := inf
		u := -1
		v := -1
		for i := range im {
			for ii := 0; ii < n; ii++ {
				if im.get(ii) != 0 {
					continue
				}
				if min > g[i][ii] {
					min = g[i][ii]
					u = i
					v = ii
				}
			}
		}
		im.increment(v)
		ans[u][v] = min
		ans[v][u] = min
	}

	sum := 0
	for i := 0; i < n-1; i++ {
		for ii := i + 1; ii < n; ii++ {
			if ans[i][ii] != -1 {
				sum += ans[i][ii]
			}
		}
	}

	fmt.Fprintln(writer, sum)
	writer.Flush()
}

// IntMap ...
type IntMap map[int]int

func (m IntMap) get(key int) int {
	if _, ok := m[key]; ok {
		return m[key]
	}
	return 0
}
func (m IntMap) increment(key int) {
	if _, ok := m[key]; ok == false {
		m[key] = 0
	}
	m[key]++
}

C++: /**
 * @brief Prim?????¢?????´????????????????????????????????????
 * @note  ??¢??£URL: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_A
 */



//****************************************
// ???????????????????????????????????????????????????
//****************************************

#include <functional>
#include <utility>
#include <algorithm>
#include <vector>
#include <cassert>
#include <tuple>
#include <queue>
#include <iostream>



//****************************************
// ???????????§????????¢?????????????????????
//****************************************

#define GRAPH_BEGIN namespace graph {
#define GRAPH_END   }



//****************************************
// ????????????????§????
//****************************************

GRAPH_BEGIN



//****************************************
// ?§????????????????
//****************************************

using weight_t   = std::int32_t;  /**< ???(u, v)????????????w?????¨?????? */
using index_t    = std::int32_t;  /**< ??????v??????????????¨??????       */
using capacity_t = weight_t;      /**< ???(u, v)??????????????¨??????    */



namespace limits {
    enum {  // scoped??§????????????????????????????????????enum(strongly-typed enum)??§?????????
        inf = std::numeric_limits<weight_t>::max() / 3,  /**< @brief ???????????¨???????????´???????????¨????????????     */
        nil = std::numeric_limits<index_t>::min() / 3,   /**< @brief ?????????????????¨???????????´???????????¨???????????? */
    };
}



/**
 * @brief  ????????????????§???????(scoped enum)
 * @detail (u, v) ??? E??§??????u??????????????°??????v?????°????????§??????
 *         ?????????????????????????????£??\????????¨?????????????????????????????§??????
 *         ??°???????????????????????£??\???????????¨???????????????????????????????????¢??????????????¨???????????????????¢?????????????
 */
enum struct vcolor : std::int32_t {
    white,  /**< ??????????????? */
    black,  /**< ??¢???????????? */
    gray,   /**< ??¢???????????? */
};

/**
 * @brief ??°????????¨?????????(??????) 
 */
struct vertex {
    union {
        weight_t d;       /**< ?§????s??????????????¢  */
        weight_t key;     /**< Prim?????¢?????´???????????????????????¨????±?????????????????????¨????????¶?????? */
    };
    index_t pi;           /**< ????????????(?????????) */
    union {
        vcolor color;     /**< ????????????        */
        bool  visited;    /**< ????????????????     */
    };
    // weight_t f;           /**< ??????????????°(DFS?????????????????????????????????????????¨??????????????????)     */
    vertex() : d(0), pi(0), color(vcolor::white)/*, f(0)*/ {}
};

/**
 * @brief ??°????????¨??¨??????(???)
 * @note  G = (V, E)???????????¢??°w???????????????????????°????????¨????????¨???
 *        ???(u, v) ??? E????????????w(u, v)??¨??¨?????????
 */
struct edge {
    index_t  src;   /**< ???????§????u */
    index_t  dst;   /**< ????????????v */
    union {
        weight_t w;     /**< ???(u, v)????????????(?????????) */
        capacity_t c;   /**< ???(u, v)????????? */
    };
    edge() = default;
    edge(index_t src, index_t dst) : src(src), dst(dst), w(1) {}
    edge(index_t src, index_t dst, weight_t w) : src(src), dst(dst), w(w) {}
};



using edges_t    = std::vector<edge>;      /**< ??°??????G=(V, E)????????????E   */
using vertices_t = std::vector<vertex>;    /**< ??°??????G=(V, E)???????????????V */
using array_t    = std::vector<weight_t>;  /**< ??????w?????????  */
using indices_t  = std::vector<index_t>;   /**< ????????????????????? */
using matrix_t   = std::vector<array_t>;   /**< ??°??????G?????£??\????????¨???(???????????¨????????¨???) */
using graph_t    = std::vector<edges_t>;   /**< ??°??????G?????£??\???????????¨???(???????????????????????¨??????) */



//****************************************
// ??¢??°?????????
//****************************************

/**< @brief ????????????????????\??????min????????????????????\????????????????????? < ??????????????? */
static bool operator < (const edge& e, const edge& f) { return e.w > f.w; }



/**
 * @brief  Prim?????¢?????´?????????
 *
 * @note   Prim?????¢?????´?????????????????°??????????????????????±???????Dijkstra?????¢?????´???????????¨?????¨?????????????????????????????????
 *         Prim?????¢?????´??????????????????A???????????????1????????¨?????¢???????????¨????????§????????????. ????????¨???????????????r??????????§???????V???????????¨?????????????????§????????????
 *         ?????????????????§??????A???????????¨???????????????(A????????¨??\?¶??????????????????????)?????£???????????????????????¨A????????????
 *         A?????????????????¨???????????????????????????????????£???A?????????????????????????????¢?????´??????????????????????????¨??????A?????????????°???¨?????¨?????¢?????????
 *         ?????????????????§?????¨?????????????¢????????????????????°????????????????????????¨????????¨???????????????????????§????????????????¬??????\??§??????
 *
 * @note   ????????????????????\?????????????????´??°????????????????????????????????????????????\???????????????????????§????????????????????\????????°?????(E)??§????????????
 *         EXTRACT-MIN????????????????????????????????§????????°????????????????????¨??§?????¨?????¨??????????????????????????(ElgV)??¨????????????
 * 
 * @param  const graph_t& G ??°??????G
 * @param  index_t        r ????°???¨?????¨??????
 */
std::pair<edges_t, weight_t> prim(const graph_t& G, index_t r)
{
    std::int32_t n = G.size();
    std::size_t m = 0;
    for (auto&& es : G) { m += es.size(); }
    std::vector<std::int32_t> visited(n);
    edges_t A; weight_t w;

    
    for (index_t u = 0; u < n; u++) {
        visited[u] = false;  // ??????????????????????????????
    }
    std::priority_queue<edge> Q;
    Q.push(edge(limits::nil, r, w = 0));    // ???r????????????0????¨??????????
    while (!Q.empty()) {
        edge e = Q.top(); Q.pop();          // ????????????????????????
        index_t u = e.dst;
        if (visited[u]) { continue; }       // ??????????????????????????¨????????§???????????´???????????????????????????????????¶???????????????
        
        for (auto&& f : G[u]) {             // u??¨??£??\????????¨????±???????????????????v?????´??°?????????
            if (!visited[f.dst/*??????v*/]) { Q.push(f); }
        }
        visited[u] = true;                  // ??????u????????????????????????
        w += e.w;                           // ????°????????????´??°??????
        if (e.src != limits::nil) {  // ??¢?????´??????????????????????????¨??????min????????????????????\???????????§?????????
            A.emplace_back(e);       // G????????????????°???¨?????¨A???A = { (v, v.??) : v ??? V - { r } }??§??????  
        }
    }
    return std::make_pair(A, w);
}


//****************************************
// ?????????????????????
//****************************************

GRAPH_END



//****************************************
// ??¨?????????????????????
//****************************************

int main(void)
{
    using namespace std;
    int n;   cin >> n;
    graph::graph_t G; G.resize(n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int k;
            cin >> k;
            if (k != -1) {
                G[i].emplace_back(i, j, k);
            }
        }
    }

    auto mst = prim(G, 0);
    cout << mst.second << endl;
    
    return 0;
}