# -*- 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 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



    # sample input when given not as adjacency matrix

    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

    '''



    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 = [[int(cost) if int(cost) != -1 else float('inf') for cost in input().split()] for i in range(n)]



    print(prim(edges, adj_matrix=True)[1])



# -*- 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 = [[int(cost) if int(cost) != -1 else float('inf') for cost in input().split()] for i in range(n)]



    print(prim(edges, adj_matrix=True)[1])



# -*- 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 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
    # sample input when given not as adjacency matrix
    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
    """
    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 = [
        [int(cost) if int(cost) != -1 else float("inf") for cost in input().split()]
        for i in range(n)
    ]
    print(prim(edges, adj_matrix=True)[1])

# -*- 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 = [
        [int(cost) if int(cost) != -1 else float("inf") for cost in input().split()]
        for i in range(n)
    ]
    print(prim(edges, adj_matrix=True)[1])

+    # 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 not as adjacency matrix -    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