# -*- coding: utf-8 -*-

def prim(edges, *, start=0, adj_matrix=False, default_value=float('inf')):

    '''

    Returns the Minimum Spanning Tree(MST) of a given graph



    # sample input when given not as adjacency list (generally works faster)

    edges = [[(1, 2), (2, 5), (3, 4)],         # node 0

             [(0, 2), (3, 3), (4, 6)],         # node 1

             [(0, 5), (3, 2), (5, 6)],         # node 2

             [(0, 4), (1, 3), (2, 2), (4, 2)], # node 3

             [(1, 6), (3, 2), (5, 4)],         # node 4

             [(2, 6), (4, 4)]]                 # node 5



    # sample input when given as adjacency matrix

    edges = [[0, 2, 5, 4, inf, inf],           # node 0

             [2, 0, inf, 3, 6, inf],           # node 1

             [5, inf, 0, 2, inf, 6],           # node 2

             [4, 3, 2, 0, 2, inf],             # node 3

             [inf, 6, inf, 2, 0, 4],           # node 4

             [inf, inf, 6, inf, 4, 0]]         # node 5

    '''



    n = len(edges)

    mst = []

    cost = 0

    T = [start]



    while True:

        tmp_edges = [(cost, (u, v)) for u in T for v, cost in enumerate(edges[u]) if cost != default_value and v not in T] if adj_matrix else\

                    [(cost, (u, v)) for u in T for v, cost in edges[u] if v not in T]



        if tmp_edges:

            min_cost, min_edge = min(tmp_edges)

            mst.append(min_edge)

            cost += min_cost

            T.append(min_edge[1])



        else:

            if len(mst) != n - 1:

                raise NoSpanningError(

                    'There is no spanning tree in this graph (search started from node{})'.

                    format(start))



            else:

                return mst, cost





class NoSpanningError(Exception):

    pass





if __name__ == '__main__':

    '''

    an example of using this function

    AIZU ONLINE JUDGE - ALDS_1_12_A

    '''



    n = int(input())

    edges = [[(j, int(cost)) for j, cost in enumerate(input().split()) if int(cost) != -1] for i in range(n)]



    print(prim(edges)[1])



# -*- coding: utf-8 -*-

from heapq import heappop, heappush





def prim(edges, *, start=0, adj_matrix=False, default_value=float('inf')):

    '''

    Returns the Minimum Spanning Tree(MST) of a given graph



    # sample input when given not as adjacency list (adj_matrix=False) (generally works faster)

    edges = [[(1, 2), (2, 5), (3, 4)],         # node 0

             [(0, 2), (3, 3), (4, 6)],         # node 1

             [(0, 5), (3, 2), (5, 6)],         # node 2

             [(0, 4), (1, 3), (2, 2), (4, 2)], # node 3

             [(1, 6), (3, 2), (5, 4)],         # node 4

             [(2, 6), (4, 4)]]                 # node 5



    # sample input when given as adjacency matrix (adj_matrix=True)

    edges = [[0, 2, 5, 4, inf, inf],           # node 0

             [2, 0, inf, 3, 6, inf],           # node 1

             [5, inf, 0, 2, inf, 6],           # node 2

             [4, 3, 2, 0, 2, inf],             # node 3

             [inf, 6, inf, 2, 0, 4],           # node 4

             [inf, inf, 6, inf, 4, 0]]         # node 5

    '''



    n = len(edges)



    costs = [float('inf')] * n

    costs[start] = 0

    prevs = [-1] * n



    pq = [(0, start)]

    T = [True] * n



    while pq:

        tmp_cost, tmp_node = heappop(pq)

        T[tmp_node] = False



        nxt_edges = ((node, cost) for node, cost in enumerate(edges[tmp_node]) if cost != default_value and T[node]) if adj_matrix else\

                    ((node, cost) for node, cost in edges[tmp_node] if T[node])



        for nxt_node, nxt_cost in nxt_edges:

            if costs[nxt_node] > nxt_cost:

                costs[nxt_node] = nxt_cost

                prevs[nxt_node] = tmp_node

                heappush(pq, (nxt_cost, nxt_node))

                T[nxt_node] = True



    else:

        if len([prev for prev in prevs if prev != -1]) != n - 1:

            raise NoSpanningError(

                'There is no spanning tree in this graph (search started from node{})'.

                format(start))



        else:

            return prevs, costs





class NoSpanningError(Exception):

    pass





if __name__ == '__main__':

    '''

    an example of using this function

    AIZU ONLINE JUDGE - ALDS_1_12_A

    '''



    n = int(input())

    edges = [[(j, int(cost)) for j, cost in enumerate(input().split())

              if int(cost) != -1] for i in range(n)]



    prevs, costs = prim(edges)

    print(sum(costs))



# -*- coding: utf-8 -*-
def prim(edges, *, start=0, adj_matrix=False, default_value=float("inf")):
    """
    Returns the Minimum Spanning Tree(MST) of a given graph
    # sample input when given not as adjacency list (generally works faster)
    edges = [[(1, 2), (2, 5), (3, 4)],         # node 0
             [(0, 2), (3, 3), (4, 6)],         # node 1
             [(0, 5), (3, 2), (5, 6)],         # node 2
             [(0, 4), (1, 3), (2, 2), (4, 2)], # node 3
             [(1, 6), (3, 2), (5, 4)],         # node 4
             [(2, 6), (4, 4)]]                 # node 5
    # sample input when given as adjacency matrix
    edges = [[0, 2, 5, 4, inf, inf],           # node 0
             [2, 0, inf, 3, 6, inf],           # node 1
             [5, inf, 0, 2, inf, 6],           # node 2
             [4, 3, 2, 0, 2, inf],             # node 3
             [inf, 6, inf, 2, 0, 4],           # node 4
             [inf, inf, 6, inf, 4, 0]]         # node 5
    """
    n = len(edges)
    mst = []
    cost = 0
    T = [start]
    while True:
        tmp_edges = (
            [
                (cost, (u, v))
                for u in T
                for v, cost in enumerate(edges[u])
                if cost != default_value and v not in T
            ]
            if adj_matrix
            else [(cost, (u, v)) for u in T for v, cost in edges[u] if v not in T]
        )
        if tmp_edges:
            min_cost, min_edge = min(tmp_edges)
            mst.append(min_edge)
            cost += min_cost
            T.append(min_edge[1])
        else:
            if len(mst) != n - 1:
                raise NoSpanningError(
                    "There is no spanning tree in this graph (search started from node{})".format(
                        start
                    )
                )
            else:
                return mst, cost


class NoSpanningError(Exception):
    pass


if __name__ == "__main__":
    """
    an example of using this function
    AIZU ONLINE JUDGE - ALDS_1_12_A
    """
    n = int(input())
    edges = [
        [(j, int(cost)) for j, cost in enumerate(input().split()) if int(cost) != -1]
        for i in range(n)
    ]
    print(prim(edges)[1])

# -*- coding: utf-8 -*-
from heapq import heappop, heappush


def prim(edges, *, start=0, adj_matrix=False, default_value=float("inf")):
    """
    Returns the Minimum Spanning Tree(MST) of a given graph
    # sample input when given not as adjacency list (adj_matrix=False) (generally works faster)
    edges = [[(1, 2), (2, 5), (3, 4)],         # node 0
             [(0, 2), (3, 3), (4, 6)],         # node 1
             [(0, 5), (3, 2), (5, 6)],         # node 2
             [(0, 4), (1, 3), (2, 2), (4, 2)], # node 3
             [(1, 6), (3, 2), (5, 4)],         # node 4
             [(2, 6), (4, 4)]]                 # node 5
    # sample input when given as adjacency matrix (adj_matrix=True)
    edges = [[0, 2, 5, 4, inf, inf],           # node 0
             [2, 0, inf, 3, 6, inf],           # node 1
             [5, inf, 0, 2, inf, 6],           # node 2
             [4, 3, 2, 0, 2, inf],             # node 3
             [inf, 6, inf, 2, 0, 4],           # node 4
             [inf, inf, 6, inf, 4, 0]]         # node 5
    """
    n = len(edges)
    costs = [float("inf")] * n
    costs[start] = 0
    prevs = [-1] * n
    pq = [(0, start)]
    T = [True] * n
    while pq:
        tmp_cost, tmp_node = heappop(pq)
        T[tmp_node] = False
        nxt_edges = (
            (
                (node, cost)
                for node, cost in enumerate(edges[tmp_node])
                if cost != default_value and T[node]
            )
            if adj_matrix
            else ((node, cost) for node, cost in edges[tmp_node] if T[node])
        )
        for nxt_node, nxt_cost in nxt_edges:
            if costs[nxt_node] > nxt_cost:
                costs[nxt_node] = nxt_cost
                prevs[nxt_node] = tmp_node
                heappush(pq, (nxt_cost, nxt_node))
                T[nxt_node] = True
    else:
        if len([prev for prev in prevs if prev != -1]) != n - 1:
            raise NoSpanningError(
                "There is no spanning tree in this graph (search started from node{})".format(
                    start
                )
            )
        else:
            return prevs, costs


class NoSpanningError(Exception):
    pass


if __name__ == "__main__":
    """
    an example of using this function
    AIZU ONLINE JUDGE - ALDS_1_12_A
    """
    n = int(input())
    edges = [
        [(j, int(cost)) for j, cost in enumerate(input().split()) if int(cost) != -1]
        for i in range(n)
    ]
    prevs, costs = prim(edges)
    print(sum(costs))

+from heapq import heappop, heappush + + -    # sample input when given not as adjacency list (generally works faster) +    # sample input when given not as adjacency list (adj_matrix=False) (generally works faster) -    # sample input when given as adjacency matrix +    # sample input when given as adjacency matrix (adj_matrix=True) -    mst = [] -    cost = 0 -    T = [start] -    while True: -        tmp_edges = ( -            [ -                (cost, (u, v)) -                for u in T -                for v, cost in enumerate(edges[u]) -                if cost != default_value and v not in T -            ] +    costs = [float("inf")] * n +    costs[start] = 0 +    prevs = [-1] * n +    pq = [(0, start)] +    T = [True] * n +    while pq: +        tmp_cost, tmp_node = heappop(pq) +        T[tmp_node] = False +        nxt_edges = ( +            ( +                (node, cost) +                for node, cost in enumerate(edges[tmp_node]) +                if cost != default_value and T[node] +            ) -            else [(cost, (u, v)) for u in T for v, cost in edges[u] if v not in T] +            else ((node, cost) for node, cost in edges[tmp_node] if T[node]) -        if tmp_edges: -            min_cost, min_edge = min(tmp_edges) -            mst.append(min_edge) -            cost += min_cost -            T.append(min_edge[1]) +        for nxt_node, nxt_cost in nxt_edges: +            if costs[nxt_node] > nxt_cost: +                costs[nxt_node] = nxt_cost +                prevs[nxt_node] = tmp_node +                heappush(pq, (nxt_cost, nxt_node)) +                T[nxt_node] = True +    else: +        if len([prev for prev in prevs if prev != -1]) != n - 1: +            raise NoSpanningError( +                "There is no spanning tree in this graph (search started from node{})".format( +                    start +                ) +            ) -            if len(mst) != n - 1: -                raise NoSpanningError( -                    "There is no spanning tree in this graph (search started from node{})".format( -                        start -                    ) -                ) -            else: -                return mst, cost +            return prevs, costs -    print(prim(edges)[1]) +    prevs, costs = prim(edges) +    print(sum(costs))