CodeEff/ECCO huggingface dataset:
# Original solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return eval(input())
     
def main():
    N = I()
    G = []
    dp = []
    for _ in range(N):
        a = LI()
        G.append(a)
        dp.append(a)

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    print((-1))
                    return 

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if j == k or k == i:
                    continue
                if dp[i][k] == inf or dp[i][j] == inf or dp[j][k] == inf:
                    continue
                if G[i][j] == G[i][k] + G[k][j]:
                    # i->jは要らない
                    dp[i][j] = inf
    cnt = 0
    for i in range(N):
        for j in range(N):
            if dp[i][j] < inf:
                cnt += dp[i][j]
    print((cnt // 2))
main()



# Optimized solution
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque
 
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7
 
DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]
 
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return eval(input())
     
def main():
    N = I()
    G = []
    for _ in range(N):
        a = LI()
        G.append(a)
    dp = copy.deepcopy(G)
    for i in range(N):
        for j in range(N):
            for k in range(N):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
 
    if dp != G:
        print((-1))
        return
 
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if j == k:
                    continue
                if i == k:
                    continue
                if dp[i][k] == 0 or dp[i][j] == 0 or dp[j][k] == 0:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    dp[i][j] = 0
                    dp[j][i] = 0
    cnt = 0
    for i in range(N):
        for j in range(N):
            cnt += dp[i][j]
    print((cnt // 2))
main()
# Original solution
import sys
import copy
n = int(eval(input()))
dist = [list(map(int,input().split())) for _ in range(n)]
e = copy.deepcopy(dist)
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j]>dist[i][k] + dist[k][j]:
                print((-1))
                sys.exit()
            if dist[i][j]==dist[i][k] + dist[k][j] and i!=j and i!=k and j!=k:
                #print(i,j,k)
                e[i][j]=float("inf")

#[print(*dist[l]) for l in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j]!=float("inf"):
            ans += dist[i][j]
print((ans//2))

# Optimized solution
import sys
import copy
n = int(eval(input()))
dist = [list(map(int,input().split())) for _ in range(n)]
e = copy.deepcopy(dist)
for k in range(n):
    for i in range(n):
        for j in range(n):
            if dist[i][j]>dist[i][k] + dist[k][j]:
                print((-1))
                sys.exit()
            if i!=j and i!=k and j!=k and dist[i][j]==dist[i][k] + dist[k][j]:
                #print(i,j,k)
                e[i][j]=float("inf")

#[print(*dist[l]) for l in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j]!=float("inf"):
            ans += dist[i][j]
print((ans//2))
# Original solution
def main():
    from heapq import heappush, heappop
    from operator import itemgetter

    n = int(eval(input()))
    a = [[int(x) for x in input().split()] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if a[i][j] != min(a[i][k] + a[k][j] for k in range(n)):
                print((-1))
                return

    h = []
    for r, row in enumerate(a):
        for c, cell in enumerate(row):
            if r == c: break
            bit = (1 << r) | (1 << c)
            heappush(h, (cell, bit))  # dist,bit

    pathes = set()
    while h:
        dist, bit = heappop(h)

        is_path = True
        for d1, p1 in pathes:
            for d2, p2 in pathes:
                xor = p1 ^ p2
                if (xor == bit) and (dist >= d1 + d2):
                    is_path = False
                    break
            if not is_path:
                break

        if is_path:
            pathes.add((dist, bit))

    print((sum(map(itemgetter(0), pathes))))


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    from heapq import heappush, heappop

    n = int(eval(input()))
    a = [[int(x) for x in input().split()] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if a[i][j] != min(a[i][k] + a[k][j] for k in range(n)):
                print((-1))
                return

    h = []
    for r, row in enumerate(a):
        for c, cell in enumerate(row):
            if r == c: break
            heappush(h, (cell, r, c))  # dist,r,c

    pathes = []
    while h:
        dist, r, c = heappop(h)

        is_path = True
        for k in range(n):
            if k == r or k == c: continue
            if dist >= a[r][k] + a[k][c]:
                is_path = False
                break

        if is_path:
            pathes.append(dist)

    print((sum(pathes)))


if __name__ == '__main__':
    main()
# Original solution
def main():
    from heapq import heappush, heappop

    n = int(eval(input()))
    a = [[int(x) for x in input().split()] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if a[i][j] != min(a[i][k] + a[k][j] for k in range(n)):
                print((-1))
                return

    h = []
    for r, row in enumerate(a):
        for c, cell in enumerate(row):
            if r == c: break
            heappush(h, (cell, r, c))  # dist,r,c

    pathes = []
    while h:
        dist, r, c = heappop(h)

        is_path = True
        for k in range(n):
            if k == r or k == c: continue
            if dist >= a[r][k] + a[k][c]:
                is_path = False
                break

        if is_path:
            pathes.append(dist)

    print((sum(pathes)))


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    n = int(eval(input()))
    a = [[int(x) for x in input().split()] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            for k in range(n):
                if a[i][j] > a[i][k] + a[k][j]:
                    print((-1))
                    return

    ret = 0
    for i in range(n):
        for j in range(i):
            for k in range(n):
                if k == i or k == j: continue
                if a[i][j] == a[i][k] + a[k][j]: break  # 辺ではない
            else:
                ret += a[i][j]

    print(ret)


if __name__ == '__main__':
    main()
# Original solution
import heapq

N = int(eval(input()))
A = [list(map(int, input().split())) for _ in range(N)]
used = [[False] * N for _ in range(N)]
ans = 0
for i in range(N):
    for j in range(N):
        via = i
        for k in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print((-1))
                exit()
            if k == i or k == j:
                continue
            if A[i][j] == A[i][k] + A[k][j]:
                via = k
        if i >= j:
            continue
        if not (used[i][via] and used[via][i]):
            used[i][via] = True
            used[via][i] = True
            ans += A[i][via]
        if not (used[via][j] and used[j][via]):
            used[via][j] = True
            used[j][via] = True
            ans += A[via][j]
print(ans)


# Optimized solution
import heapq

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

ans = 0
for i in range(N):
    for j in range(N):
        via_k = float('inf')
        for k in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print((-1))
                exit()
            if k == i or k == j:
                continue
            via_k = min(via_k, A[i][k] + A[k][j])
        if i <= j:
            continue
        if A[i][j] < via_k:
            ans += A[i][j]
print(ans)
# Original solution
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
"""
a,b,c,d,e,f = LI()
a *= 100
b *= 100
ans = [a,0]
for i in range(f//a+1):
    for j in range((f-a*i)//b+1):
        for k in range((f-a*i-b*j)//c+1):
            for l in range((f-a*i-b*j-c*k)//d+1):
                if i or j or k or l:
                    s = c*k+d*l
                    w = a*i+b*j
                    q = w*e//100
                    if s <= q:
                        if w+s <= f:
                            if ans[1]/ans[0] < s/(s+w):
                                ans = [w+s,s]
print(*ans)
"""

#D
n = I()
d = LIR(n)
l = [[1 for j in range(n)] for i in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            if d[i][j] > d[i][k]+d[k][j]:
                print((-1))
                quit()
            if d[i][j] == d[i][k]+d[k][j]:
                l[i][j] = l[i][k]+l[k][j]

ans = 0
for i in range(n):
    for j in range(n):
        if l[i][j] == 4:
            ans += d[i][j]
ans //= 2
print(ans)
#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


# Optimized solution
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    d = LIR(n)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k]+d[k][j] < d[i][j]:
                    print((-1))
                    return
    ans = 0
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if k in (i,j):
                    continue
                if d[i][k]+d[k][j] <= d[i][j]:
                    break
            else:                
                ans += d[i][j]
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()
# Original solution
import copy
from itertools import product, combinations

N = int(eval(input()))

dp = []
for _ in range(N):
    dp.append(list(map(int, input().split(' '))))

original = copy.deepcopy(dp)


for k, i, j in product(list(range(N)), repeat=3):
    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

if dp == original:
    route_set = set()
    costs = []
    for i in range(N):
        for j in range(i + 1, N):
            route_set.add(dp[i][j])
            costs.append(dp[i][j])

    route_set = route_set - set(map(sum, combinations(costs, r=2)))
    print((sum([cost for cost in costs if cost in route_set])))
else:
    print((-1))


# Optimized solution
import copy
from itertools import product, combinations

N = int(eval(input()))

dp = []
for _ in range(N):
    dp.append(list(map(int, input().split(' '))))

original = copy.deepcopy(dp)

for k, i, j in product(list(range(N)), repeat=3):
    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

if dp == original:
    cost = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                if k == i or k == j:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    break
            else:
                cost += dp[i][j]
    print(cost)
else:
    print((-1))
# Original solution
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(eval(input()))
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a in range(N):
        for b, l in enumerate(A[a]):
            for k in range(N):
                if k != a and k != b:
                    if l >  A[a][k] + A[k][b]:
                        possible = False
                        break
                    elif l ==  A[a][k] + A[k][b]:
                        break
            else: length += l
        if not possible:
            print((-1))
            break
    else: print((length // 2))
    
    return 0
  
if __name__ == "__main__":
    solve()


# Optimized solution
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(eval(input()))
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(list(range(N)), 2):
        Lab = A[a][b]
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    break
        else: length += Lab
        if not possible:
            print((-1))
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()
# Original solution
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(eval(input()))
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(list(range(N)), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print((-1))
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

# Optimized solution
import sys
from itertools import combinations
  
def solve():
    input = sys.stdin.readline
    N = int(eval(input()))
    A = dict()
    for i in range(N):
        A[i] = dict()
        for j, a in enumerate(list(map(int, input().split()))): A[i][j] = a

    length = 0
    possible = True
    for a, b in combinations(list(range(N)), 2):
        Lab = A[a][b]
        for k in range(N):
            if k != a and k != b:
                if Lab < A[a][k] + A[k][b]: continue
                if Lab >  A[a][k] + A[k][b]: possible = False
                break
        else: length += Lab
        if possible: continue
        print((-1))
        break
    else: print(length)
    
    return 0
 
if __name__ == "__main__":
    solve()
# Original solution
import sys
from itertools import permutations, combinations

N=eval(input())
d=[ [ float("inf") for j in range(N+1) ] for i in range(N+1) ] 

hen=[ [ 0 for j in range(N+1) ] for i in range(N+1) ] 
ans=0
for i in range(N):
	L=list(map(int, sys.stdin.readline().split()))
	d[i][i]=0
	for j in range(i+1,N):
		lengh=L[j]
		d[i+1][j+1]=lengh
		d[j+1][i+1]=lengh
		hen[i+1][j+1]=lengh
		ans+=lengh

d[N][N]=0

P=list( permutations(list(range(1,N+1)),3) )

for i,j,k in P:
	a=d[i][j]
	b=d[j][k]
	c=d[i][k]	
	if a+b<c:
		print(-1)
		quit()
	if a+b==c and hen[i][k]!=0:
		ans-=c
		hen[i][k]=0
		hen[k][i]=0

print(ans)


# Optimized solution
import sys
from itertools import permutations, combinations

N=eval(input())
d=[ [ float("inf") for j in range(N+1) ] for i in range(N+1) ] 

KOUHO=[]
for i in range(N):
	L=list(map(int, sys.stdin.readline().split()))
	d[i][i]=0
	for j in range(i+1,N):
		length=L[j]
		d[i+1][j+1]=length
		d[j+1][i+1]=length
		KOUHO.append( (length,i+1,j+1))


ans=0
for c,i,j in KOUHO:
	for k in range(1,N+1):
		if k==i or k==j: continue
		a=d[i][k]
		b=d[j][k]
		if a+b==c:
			break
		elif a+b<c:
			print(-1)
			quit()
	else:
		ans+=c

print(ans)
# Original solution
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = [[int(i) for i in readline().split()] for _ in range(N)]

    via_min = [[10**15] * N for _ in range(N)]

    for i in range(N):
        for j in range(N):
            for k in range(N):
                if k == i or k == j:
                    continue
                via_min[i][j] = min(via_min[i][j], A[i][k] + A[k][j]) 

    ans = 0
    for i in range(N):
        for j in range(i+1,N):
            if via_min[i][j] < A[i][j]:
                print((-1))
                exit()
            elif via_min[i][j] == A[i][j]:
                continue
            else:
                ans += A[i][j]
    
    print(ans)


if __name__ == "__main__":
    main()


# Optimized solution
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = [[int(i) for i in readline().split()] for _ in range(N)]

    via_min = [[10**15] * N for _ in range(N)]

    ans = 0
    for i in range(N-1):
        for j in range(i+1,N):
            d = A[i][j]
            flag = True
            for k in range(N):
                if k == i or k == j:
                    continue
                
                tmp = A[i][k] + A[k][j]
                if tmp < d:
                    print((-1))
                    exit()
                
                elif tmp == d:
                    flag = False
                    break
            if flag:
                ans += d
    
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
import heapq
INFTY = 10**12
def dist(cur,b):
    d = [INFTY for _ in range(N)]
    d[cur[1]] = 0
    hist = [0 for _ in range(N)]
    hist[cur[1]] = 1
    heap = [cur]
    while heap:
        cur = heapq.heappop(heap)
        hist[cur[1]] = 1
        for x in B[cur[1]]:
            if hist[x[1]]==0:
                if d[x[1]]>cur[0]+x[0]:
                    d[x[1]] = cur[0]+x[0]
                    heapq.heappush(heap,(d[x[1]],x[1]))
    return d[b]
N = int(eval(input()))
A = {(i,j):INFTY for i in range(N) for j in range(N)}
for i in range(N):
    row = list(map(int,input().split()))
    for j in range(N):
        A[(i,j)] = row[j]
G = list(A.items())
G = sorted(G,key=lambda x:x[1])
B = {i:[] for i in range(N)}
ind = 0
for x in G:
    a,b = x[0][0],x[0][1]
    d = x[1]
    if d>0:
        dmin = dist([0,a],b)
#         print("dmin({},{})={}".format(a,b,dmin))
        if dmin>d:
            if (d,b) not in B[a]:
                B[a].append((d,b))
            if (d,a) not in B[b]:
                B[b].append((d,a))
        elif d>dmin:
            ind = 1
            break
#         print("B={}".format(B))
if ind==1:
    print((-1))
else:
    cnt = 0
    for a in B:
        for x in B[a]:
            cnt += x[0]
    print((cnt//2))

# Optimized solution
N = int(eval(input()))
A = [list(map(int,input().split())) for _ in range(N)]
cnt = 0
for i in range(N-1):
    for j in range(i+1,N):
        amin = 10**10
        for k in range(N):
            if k!=i and k!=j:
                amin = min(amin,A[i][k]+A[k][j])
        if A[i][j]>amin:
            cnt = -1
            break
        elif A[i][j]<amin:
            cnt += A[i][j]
    if cnt==-1:break
print(cnt)
# Original solution
N = int(eval(input()))
A = [list(map(int,input().split())) for _ in range(N)]
cnt = 0
for i in range(N):
    for j in range(N):
        cnt += A[i][j]
flg = 0
B = [[0 for _ in range(N)] for _ in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j]>A[i][k]+A[k][j]:
                flg = -1
                break
            elif A[i][j]==A[i][k]+A[k][j] and A[i][k]*A[k][j]>0 and B[i][j]==0:
                cnt -= A[i][j]
                B[i][j]=1
        if flg==-1:break
    if flg==-1:break
if flg==-1:
    print((-1))
else:
    print((cnt//2))          

# Optimized solution
N = int(eval(input()))
A = [[0 for _ in range(N+1)]]
for _ in range(N):
    a = list(map(int,input().split()))
    a.insert(0,0)
    A.append(a)
tot = 0
for i in range(1,N):
    for j in range(i,N+1):
        tot += A[i][j]
for i in range(1,N):
    for j in range(i+1,N+1):
        for k in range(1,N+1):
            if k!=i and k!=j:
                if A[i][j]>A[i][k]+A[k][j]:
                    tot = -1
                    break
                elif A[i][j]==A[i][k]+A[k][j]:
                    tot -= A[i][j]
                    break
        if tot<0:break
    if tot<0:break
print(tot)
# Original solution
from heapq import heappop, heappush


def bfs(x, y):
    path = [float('inf')] * N
    q = []
    heappush(q, (0, x))
    path[x] = 0

    while q:
        s, p = heappop(q)
        for np, d in edge[p]:
            nd = path[p] + d
            if path[np] > nd:
                path[np] = nd
                heappush(q, (nd, np))
    
    return path[y]


N = int(eval(input()))
A = [list(map(int, input().split())) for _ in range(N)]
q = []
for i in range(N):
    for j in range(i + 1, N):
        q.append((A[i][j], i, j))

q.sort()

# B = [[float('inf')] * N for _ in range(N)]

ans = 0
edge = [[] for _ in range(N)]
for a, i, j in q:
    b = bfs(i, j)
    if a < b:
        edge[i].append((j, a))
        edge[j].append((i, a))
        ans += a
    elif a == b:
        pass
    else:
        print((-1))
        exit()

print(ans)


# Optimized solution
N = int(eval(input()))
A = [list(map(int, input().split())) for _ in range(N)]

dp = A
cnt = 0
for i in range(N):
    for j in range(N):
        if all(dp[i][j] < dp[i][k] + dp[k][j] for k in range(N) if k != i and k != j):
            cnt += dp[i][j]
        if any(dp[i][j] > dp[i][k] + dp[k][j] for k in range(N)):
            print((-1))
            exit()

print((cnt // 2))
# Original solution
N = int(eval(input()))
A = [list(map(int, input().split())) for _ in range(N)]

dp = A
cnt = 0
for i in range(N):
    for j in range(N):
        if all(dp[i][j] < dp[i][k] + dp[k][j] for k in range(N) if k != i and k != j):
            cnt += dp[i][j]
        if any(dp[i][j] > dp[i][k] + dp[k][j] for k in range(N)):
            print((-1))
            exit()

print((cnt // 2))


# Optimized solution
N = int(eval(input()))
A = [list(map(int, input().split())) for _ in range(N)]

dp = A
cnt = 0
for i in range(N - 1):
    for j in range(i + 1, N):
        if all(dp[i][j] < dp[i][k] + dp[k][j] for k in range(N) if k != i and k != j):
            cnt += dp[i][j]
        if any(dp[i][j] > dp[i][k] + dp[k][j] for k in range(N)):
            print((-1))
            exit()

print(cnt)