import array

import collections

import heapq



INF = 1e9



N = int(eval(input()))



AdjacentVertex = collections.namedtuple('AdjacentVertex', 'vertex cost')

adjacency_list = collections.defaultdict(set)



NO_VERTEX = -1

 

def compute_mst_prim(max_v, adj_list):

    pred = collections.defaultdict(lambda: NO_VERTEX)

    key = collections.defaultdict(lambda: INF)

    key[0] = 0

    pq = [(key[v], v) for v in range(max_v)]

    heapq.heapify(pq)

    in_pq = array.array("B", (True for _ in range(max_v)))

    while pq:

        _, u = heapq.heappop(pq)

        in_pq[u] = False

        for v, v_cost in adj_list[u]:

            if in_pq[v]:

                weight = v_cost

                if weight < key[v]:

                    pred[v] = u

                    key[v] = weight

                    heapq.heappush(pq, (weight, v))

                    in_pq[v] = True

    return (pred, key)



for i in range(N):

    u = list(map(int, input().split()))

    for j in range(N):

        if u[j] == -1:

            adjacency_list[i].add(AdjacentVertex(j, INF))

            adjacency_list[j].add(AdjacentVertex(i, INF))

        else:

            adjacency_list[i].add(AdjacentVertex(j, u[j]))

            adjacency_list[j].add(AdjacentVertex(i, u[j]))



(_, key) = compute_mst_prim(N, adjacency_list)



print((sum(key.values())))
INF = 1e9



n = int(eval(input()))

adj_matrix = [list(map(int, input().split())) for i in range(n)]





def prim(x):

    isVisited = [False] * x

    d = [INF] * x 

    d[0] = 0

    p = [-1] * x 

    

    while True:

        min_cost = INF

        

        for i in range(x):

            if isVisited[i] != True and d[i] < min_cost:

                min_cost = d[i]

                u = i

        

        if min_cost == INF:

            break

        

        isVisited[u] = True

        

        for v in range(x):

            if isVisited[v] != True and adj_matrix[u][v] != -1:

                if adj_matrix[u][v] < d[v]:

                    d[v] = adj_matrix[u][v]

                    p[v] = u

    return sum(d)



print((prim(n)))
import array
import collections
import heapq

INF = 1e9
N = int(eval(input()))
AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost")
adjacency_list = collections.defaultdict(set)
NO_VERTEX = -1


def compute_mst_prim(max_v, adj_list):
    pred = collections.defaultdict(lambda: NO_VERTEX)
    key = collections.defaultdict(lambda: INF)
    key[0] = 0
    pq = [(key[v], v) for v in range(max_v)]
    heapq.heapify(pq)
    in_pq = array.array("B", (True for _ in range(max_v)))
    while pq:
        _, u = heapq.heappop(pq)
        in_pq[u] = False
        for v, v_cost in adj_list[u]:
            if in_pq[v]:
                weight = v_cost
                if weight < key[v]:
                    pred[v] = u
                    key[v] = weight
                    heapq.heappush(pq, (weight, v))
                    in_pq[v] = True
    return (pred, key)


for i in range(N):
    u = list(map(int, input().split()))
    for j in range(N):
        if u[j] == -1:
            adjacency_list[i].add(AdjacentVertex(j, INF))
            adjacency_list[j].add(AdjacentVertex(i, INF))
        else:
            adjacency_list[i].add(AdjacentVertex(j, u[j]))
            adjacency_list[j].add(AdjacentVertex(i, u[j]))
(_, key) = compute_mst_prim(N, adjacency_list)
print((sum(key.values())))

INF = 1e9
n = int(eval(input()))
adj_matrix = [list(map(int, input().split())) for i in range(n)]


def prim(x):
    isVisited = [False] * x
    d = [INF] * x
    d[0] = 0
    p = [-1] * x
    while True:
        min_cost = INF
        for i in range(x):
            if isVisited[i] != True and d[i] < min_cost:
                min_cost = d[i]
                u = i
        if min_cost == INF:
            break
        isVisited[u] = True
        for v in range(x):
            if isVisited[v] != True and adj_matrix[u][v] != -1:
                if adj_matrix[u][v] < d[v]:
                    d[v] = adj_matrix[u][v]
                    p[v] = u
    return sum(d)


print((prim(n)))

-import array -import collections -import heapq - -N = int(eval(input())) -AdjacentVertex = collections.namedtuple("AdjacentVertex", "vertex cost") -adjacency_list = collections.defaultdict(set) -NO_VERTEX = -1 +n = int(eval(input())) +adj_matrix = [list(map(int, input().split())) for i in range(n)] -def compute_mst_prim(max_v, adj_list): -    pred = collections.defaultdict(lambda: NO_VERTEX) -    key = collections.defaultdict(lambda: INF) -    key[0] = 0 -    pq = [(key[v], v) for v in range(max_v)] -    heapq.heapify(pq) -    in_pq = array.array("B", (True for _ in range(max_v))) -    while pq: -        _, u = heapq.heappop(pq) -        in_pq[u] = False -        for v, v_cost in adj_list[u]: -            if in_pq[v]: -                weight = v_cost -                if weight < key[v]: -                    pred[v] = u -                    key[v] = weight -                    heapq.heappush(pq, (weight, v)) -                    in_pq[v] = True -    return (pred, key) +def prim(x): +    isVisited = [False] * x +    d = [INF] * x +    d[0] = 0 +    p = [-1] * x +    while True: +        min_cost = INF +        for i in range(x): +            if isVisited[i] != True and d[i] < min_cost: +                min_cost = d[i] +                u = i +        if min_cost == INF: +            break +        isVisited[u] = True +        for v in range(x): +            if isVisited[v] != True and adj_matrix[u][v] != -1: +                if adj_matrix[u][v] < d[v]: +                    d[v] = adj_matrix[u][v] +                    p[v] = u +    return sum(d) -for i in range(N): -    u = list(map(int, input().split())) -    for j in range(N): -        if u[j] == -1: -            adjacency_list[i].add(AdjacentVertex(j, INF)) -            adjacency_list[j].add(AdjacentVertex(i, INF)) -        else: -            adjacency_list[i].add(AdjacentVertex(j, u[j])) -            adjacency_list[j].add(AdjacentVertex(i, u[j])) -(_, key) = compute_mst_prim(N, adjacency_list) -print((sum(key.values()))) +print((prim(n)))