import sys

from copy import deepcopy as dc

input = sys.stdin.buffer.readline

N = int(eval(input()))

d = [list(map(int, input().split())) for _ in range(N)]

d2 = dc(d)

for k in range(N):

  for i in range(N):

    for j in range(N):

      d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])

f = 0

for i in range(N):

  for j in range(N):

    if d[i][j] != d2[i][j]:

      f = 1

if f:

  print((-1))

else:

  res = 0

  for i in range(N):

    for j in range(N):

      x = 1

      for k in range(N):

        if k != i and k != j:

          if d[i][j] == d[i][k] + d[k][j]: x = 0

      res += x * d[i][j]

          

  print((res // 2))
N = int(eval(input()))

a = [list(map(int, input().split())) for _ in range(N)]

b = [a[i][: ] for i in range(N)]

for k in range(N):

 for i in range(N):

  for j in range(N):

   b[i][j] = min(b[i][j], b[i][k] + b[k][j])

inf = 10 ** 10

if a == b:

 dp = [[inf] * N for _ in range(N)]

 for i in range(N):

  for j in range(N):

   mn = i

   for k in range(N):

    if k == j: continue

    if a[i][k] + a[k][j] == a[i][j]:

     if a[mn][j] > a[k][j]:

      mn = k

   if dp[mn][j] == inf:

    dp[mn][j] = a[mn][j]

   elif dp[mn][j] != a[mn][j]:

    print((-1))

    exit(0)

 for i in range(N):

  for j in range(N):

   if dp[i][j] == inf: dp[i][j] = 0

 print((sum([sum(dp[i]) for i in range(N)]) // 2))

else: print((-1))
import sys
from copy import deepcopy as dc

input = sys.stdin.buffer.readline
N = int(eval(input()))
d = [list(map(int, input().split())) for _ in range(N)]
d2 = dc(d)
for k in range(N):
    for i in range(N):
        for j in range(N):
            d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])
f = 0
for i in range(N):
    for j in range(N):
        if d[i][j] != d2[i][j]:
            f = 1
if f:
    print((-1))
else:
    res = 0
    for i in range(N):
        for j in range(N):
            x = 1
            for k in range(N):
                if k != i and k != j:
                    if d[i][j] == d[i][k] + d[k][j]:
                        x = 0
            res += x * d[i][j]
    print((res // 2))

N = int(eval(input()))
a = [list(map(int, input().split())) for _ in range(N)]
b = [a[i][:] for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            b[i][j] = min(b[i][j], b[i][k] + b[k][j])
inf = 10**10
if a == b:
    dp = [[inf] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            mn = i
            for k in range(N):
                if k == j:
                    continue
                if a[i][k] + a[k][j] == a[i][j]:
                    if a[mn][j] > a[k][j]:
                        mn = k
            if dp[mn][j] == inf:
                dp[mn][j] = a[mn][j]
            elif dp[mn][j] != a[mn][j]:
                print((-1))
                exit(0)
    for i in range(N):
        for j in range(N):
            if dp[i][j] == inf:
                dp[i][j] = 0
    print((sum([sum(dp[i]) for i in range(N)]) // 2))
else:
    print((-1))

-import sys -from copy import deepcopy as dc - -input = sys.stdin.buffer.readline -d = [list(map(int, input().split())) for _ in range(N)] -d2 = dc(d) +a = [list(map(int, input().split())) for _ in range(N)] +b = [a[i][:] for i in range(N)] -            d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j]) -f = 0 -for i in range(N): -    for j in range(N): -        if d[i][j] != d2[i][j]: -            f = 1 -if f: -    print((-1)) -else: -    res = 0 +            b[i][j] = min(b[i][j], b[i][k] + b[k][j]) +inf = 10**10 +if a == b: +    dp = [[inf] * N for _ in range(N)] -            x = 1 +            mn = i -                if k != i and k != j: -                    if d[i][j] == d[i][k] + d[k][j]: -                        x = 0 -            res += x * d[i][j] -    print((res // 2)) +                if k == j: +                    continue +                if a[i][k] + a[k][j] == a[i][j]: +                    if a[mn][j] > a[k][j]: +                        mn = k +            if dp[mn][j] == inf: +                dp[mn][j] = a[mn][j] +            elif dp[mn][j] != a[mn][j]: +                print((-1)) +                exit(0) +    for i in range(N): +        for j in range(N): +            if dp[i][j] == inf: +                dp[i][j] = 0 +    print((sum([sum(dp[i]) for i in range(N)]) // 2)) +else: +    print((-1))