

def warshall_floyd(cost):

    ret = [[1]*N for _ in [0]*N]

    for k in range(N):

        for i, c_left in enumerate(cost[i][k] for i in range(N)):

            for j, (c_now, c_right) in enumerate(zip(cost[i], cost[k])):

                if c_left + c_right < c_now:

                    print((-1))

                    exit()

                if i == j or j == k or k == i:

                    continue

                if c_left + c_right == c_now:

                    ret[i][j] = ret[j][i] = 0

    return ret





INF = 10**10

N, *A = list(map(int, open(0).read().split()))

*A, = list(zip(*[iter(A)]*N))





E = []

for i in range(N):

    for j in range(i+1, N):

        E.append((A[i][j], i, j))

E.sort()



road = warshall_floyd(A)

ans = 0

for cost, i, j in E:

    if not road[i][j]:

        continue

    ans += cost



print(ans)

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

import numpy as np

N = int(eval(input()))

A = np.array([list(map(int, input().split())) for _ in [0]*N], dtype=np.int)

D = csgraph_from_dense(A)

D = floyd_warshall(D, directed=False)



if (A == D).all():

    ans = 0

    D += np.identity(N, int) * (1 << 60)

    for i in range(N):

        for j in range(i+1, N):

            a = np.min(D[i]+D[j])

            if a > D[i, j]:

                ans += D[i, j]

    print((int(ans)))

else:

    print((-1))

def warshall_floyd(cost):
    ret = [[1] * N for _ in [0] * N]
    for k in range(N):
        for i, c_left in enumerate(cost[i][k] for i in range(N)):
            for j, (c_now, c_right) in enumerate(zip(cost[i], cost[k])):
                if c_left + c_right < c_now:
                    print((-1))
                    exit()
                if i == j or j == k or k == i:
                    continue
                if c_left + c_right == c_now:
                    ret[i][j] = ret[j][i] = 0
    return ret


INF = 10**10
N, *A = list(map(int, open(0).read().split()))
(*A,) = list(zip(*[iter(A)] * N))
E = []
for i in range(N):
    for j in range(i + 1, N):
        E.append((A[i][j], i, j))
E.sort()
road = warshall_floyd(A)
ans = 0
for cost, i, j in E:
    if not road[i][j]:
        continue
    ans += cost
print(ans)

from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
import numpy as np

N = int(eval(input()))
A = np.array([list(map(int, input().split())) for _ in [0] * N], dtype=np.int)
D = csgraph_from_dense(A)
D = floyd_warshall(D, directed=False)
if (A == D).all():
    ans = 0
    D += np.identity(N, int) * (1 << 60)
    for i in range(N):
        for j in range(i + 1, N):
            a = np.min(D[i] + D[j])
            if a > D[i, j]:
                ans += D[i, j]
    print((int(ans)))
else:
    print((-1))

-def warshall_floyd(cost): -    ret = [[1] * N for _ in [0] * N] -    for k in range(N): -        for i, c_left in enumerate(cost[i][k] for i in range(N)): -            for j, (c_now, c_right) in enumerate(zip(cost[i], cost[k])): -                if c_left + c_right < c_now: -                    print((-1)) -                    exit() -                if i == j or j == k or k == i: -                    continue -                if c_left + c_right == c_now: -                    ret[i][j] = ret[j][i] = 0 -    return ret +from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall +import numpy as np - -INF = 10**10 -N, *A = list(map(int, open(0).read().split())) -(*A,) = list(zip(*[iter(A)] * N)) -E = [] -for i in range(N): -    for j in range(i + 1, N): -        E.append((A[i][j], i, j)) -E.sort() -road = warshall_floyd(A) -ans = 0 -for cost, i, j in E: -    if not road[i][j]: -        continue -    ans += cost -print(ans) +N = int(eval(input())) +A = np.array([list(map(int, input().split())) for _ in [0] * N], dtype=np.int) +D = csgraph_from_dense(A) +D = floyd_warshall(D, directed=False) +if (A == D).all(): +    ans = 0 +    D += np.identity(N, int) * (1 << 60) +    for i in range(N): +        for j in range(i + 1, N): +            a = np.min(D[i] + D[j]) +            if a > D[i, j]: +                ans += D[i, j] +    print((int(ans))) +else: +    print((-1))