from sys import stdin

INF = 1<<21

WHITE = 0

GRAY = 1

BLACK = 2

n = int(stdin.readline())

M = [[INF] * (n + 1) for _ in range(n + 1)]

for i in range(0, n):

    for j, e in enumerate(list(map(int, stdin.readline().split()))):

        if e != -1: M[i][j] = e

d = [INF] * n

d[0] = 0

t = [-1] * n

color = [0] * n

def prim():

    while True:

        minv = INF

        u = -1

        for i in range(0, n):

            if minv > d[i] and color[i] != BLACK:

                u = i

                minv = d[i]

        if u == -1: break

        color[u] = BLACK

        for v in range(0, n):

            if color[v] != BLACK and d[v] > M[u][v]:

                d[v] = M[u][v]

                t[v] = u

                color[v] = GRAY

    return sum(d)

print((prim()))
from sys import stdin

INF = 1<<21

WHITE, GRAY, BLACK = 0, 1, 2

n = int(stdin.readline())

M = [[INF] * n for _ in range(n)]

for i in range(0, n):

    for j, e in enumerate(list(map(int, stdin.readline().split()))):

        if e != -1: M[i][j] = e

d = [INF] * n

d[0] = 0

color = [0] * n

def prim():

    while True:

        minv = INF

        u = -1

        for i in range(0, n):

            if minv > d[i] and color[i] != BLACK:

                u = i

                minv = d[i]

        if u == -1: break

        color[u] = BLACK

        for v in range(0, n):

            if color[v] != BLACK and d[v] > M[u][v]:

                d[v] = M[u][v]

    return sum(d)

print((prim()))
from sys import stdin

INF = 1 << 21
WHITE = 0
GRAY = 1
BLACK = 2
n = int(stdin.readline())
M = [[INF] * (n + 1) for _ in range(n + 1)]
for i in range(0, n):
    for j, e in enumerate(list(map(int, stdin.readline().split()))):
        if e != -1:
            M[i][j] = e
d = [INF] * n
d[0] = 0
t = [-1] * n
color = [0] * n


def prim():
    while True:
        minv = INF
        u = -1
        for i in range(0, n):
            if minv > d[i] and color[i] != BLACK:
                u = i
                minv = d[i]
        if u == -1:
            break
        color[u] = BLACK
        for v in range(0, n):
            if color[v] != BLACK and d[v] > M[u][v]:
                d[v] = M[u][v]
                t[v] = u
                color[v] = GRAY
    return sum(d)


print((prim()))

from sys import stdin

INF = 1 << 21
WHITE, GRAY, BLACK = 0, 1, 2
n = int(stdin.readline())
M = [[INF] * n for _ in range(n)]
for i in range(0, n):
    for j, e in enumerate(list(map(int, stdin.readline().split()))):
        if e != -1:
            M[i][j] = e
d = [INF] * n
d[0] = 0
color = [0] * n


def prim():
    while True:
        minv = INF
        u = -1
        for i in range(0, n):
            if minv > d[i] and color[i] != BLACK:
                u = i
                minv = d[i]
        if u == -1:
            break
        color[u] = BLACK
        for v in range(0, n):
            if color[v] != BLACK and d[v] > M[u][v]:
                d[v] = M[u][v]
    return sum(d)


print((prim()))

-WHITE = 0 -GRAY = 1 -BLACK = 2 +WHITE, GRAY, BLACK = 0, 1, 2 -M = [[INF] * (n + 1) for _ in range(n + 1)] +M = [[INF] * n for _ in range(n)] -t = [-1] * n -                t[v] = u -                color[v] = GRAY