Problem:
 Score : 500 points    Problem Statement In Takahashi Kingdom, which once existed, there are N cities, and some pairs of cities are connected bidirectionally by roads.
The following are known about the road network:   People traveled between cities only through roads. It was possible to reach any city from any other city, via intermediate cities if necessary.  Different roads may have had different lengths, but all the lengths were positive integers.   Snuke the archeologist found a table with N rows and N columns, A , in the ruin of Takahashi Kingdom.
He thought that it represented the shortest distances between the cities along the roads in the kingdom.  Determine whether there exists a road network such that for each u and v , the integer A_{u, v} at the u -th row and v -th column of A is equal to the length of the shortest path from City u to City v .
If such a network exist, find the shortest possible total length of the roads.      Constraints  1 \leq N \leq 300  If i ≠ j , 1 \leq A_{i, j} = A_{j, i} \leq 10^9 .  A_{i, i} = 0         Inputs Input is given from Standard Input in the following format:  N  A_{1, 1}  A_{1, 2}  ...  A_{1, N}  A_{2, 1}  A_{2, 2}  ...  A_{2, N}  ...  A_{N, 1}  A_{N, 2}  ...  A_{N, N}       Outputs If there exists no network that satisfies the condition, print -1 .
If it exists, print the shortest possible total length of the roads.        Sample Input 1 3
0 1 3
1 0 2
3 2 0      Sample Output 1 3  The network below satisfies the condition:   City 1 and City 2 is connected by a road of length 1 .  City 2 and City 3 is connected by a road of length 2 .  City 3 and City 1 is not connected by a road.        Sample Input 2 3
0 1 3
1 0 1
3 1 0      Sample Output 2 -1  As there is a path of length 1 from City 1 to City 2 and City 2 to City 3 , there is a path of length 2 from City 1 to City 3 .
However, according to the table, the shortest distance between City 1 and City 3 must be 3 .  Thus, we conclude that there exists no network that satisfies the condition.       Sample Input 3 5
0 21 18 11 28
21 0 13 10 26
18 13 0 23 13
11 10 23 0 17
28 26 13 17 0      Sample Output 3 82       Sample Input 4 3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0      Sample Output 4 3000000000

Solution (Python):
from functools import reduce
import math
import copy

def main():
    
    
    
    

    
    
    
    
    
    

    
    

    
    
    
    
    
    
    
    
    
    INF = float("inf")

    
    MOD = 10**9+7
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    
    
    N = int(input())
    a = []
    ans = 0
    for i in range(N):
        a.append(list(int(_) for _ in input().split()))
    d = copy.deepcopy(a)
    
    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]:
                    print(-1)
                    exit()
                elif a[i][j] == a[i][k]+a[k][j] and a[i][j] != 0 and k!=i and k!=j:
                    d[i][j] = 0
          
    for i in range(N):
        ans += sum(d[i])
    print(ans//2)
    
if __name__ == '__main__':
    main()

Solution (Python):
import heapq
INF = 10**10
n = int(input())
a = [[int(item) for item in input().split()] for _ in range(n)]
b = [[INF for _ in range(n)] for _ in range(n)]

ans = 0
for i in range(n):
    ans += sum(a[i])
    a[i][i] = INF
ans //= 2

for i in range(n):
    for j in range(i):
        bipas = min(map(sum, zip(a[i], a[j])))
        if a[i][j] > bipas:
            print(-1)
            exit()
        if a[i][j] == bipas:
            ans -= a[i][j]
print(ans)

Solution (Python):
import itertools, sys

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

exists = [[True] * n for _ in range(n)]
for k, i, j in itertools.product(range(n), repeat=3):
    if a[i][k] + a[k][j] == a[i][j] and i != k and k != j:
        exists[i][j] = False
    elif a[i][k] + a[k][j] < a[i][j]:
        print(-1)
        sys.exit()

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if exists[i][j]:
            ans += a[i][j]
print(ans)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import floyd_warshall as wf
n=int(input())
s=np.array([list(map(int,input().split()))for i in range(n)])
if np.any(s!=wf(s,directed=False)):
    print(-1)
else:
    c=0
    for i in range(n):
        s[i][i]=10**10
    for i in range(n):
        for j in range(i+1,n):
            d=np.min(s[i]+s[j])
            if s[i,j]!=d:
                c+=s[i,j]
    else:
        print(c)

Solution (Python):
import numpy as np
N=int(input())
A=[np.array(list(map(int,input().split()))) for i in range(N)]
ans=sum([sum(A[i]) for i in range(N)])
ans//=2
for i in range(N):
    A[i][i]=10**10
def main(ans):
    for i in range(N):
        for j in range(i+1,N):
            Min=min(A[i]+A[j])
            if Min<A[i][j]:
                return -1
            if Min==A[i][j]:
                ans-=A[i][j]
    return ans
print(main(ans))

Solution (Python):
import numpy as np
N=int(input())
A=[np.array(list(map(int,input().split()))) for i in range(N)]
ans=sum([sum(A[i]) for i in range(N)])
ans//=2
for i in range(N):
    A[i][i]=10**10
def main(ans):
    for i in range(N):
        for j in range(i+1,N):
            Min=np.min(A[i]+A[j])
            if Min<A[i][j]:
                return -1
            if Min==A[i][j]:
                ans-=A[i][j]
    return ans
print(main(ans))

Solution (Python):
import sys
input=sys.stdin.readline
N=int(input())
dist=[list(map(int,input().split())) for i in range(N)]
ans=sum([sum(dist[i]) for i in range(N)])
for i in range(N):
    dist[i][i]=float('inf')
ans//=2
def main(ans):
    for i in range(N):
        for j in range(i+1,N):
            Min=min(map(sum,zip(dist[i],dist[j])))
            if Min<dist[i][j]:
                return -1
            if Min==dist[i][j]:
                ans-=dist[i][j] 
    return ans
print(main(ans))

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]

    INF = 10**10
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            bipas = min(map(sum, zip(A[i], A[j])))

            if A[i][j] > bipas:
                print(-1)
                return 0
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N = int(input())
    A = np.array([list(map(int, input().split())) for i in range(N)])
    
    

    INF = 10**10
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            
            bipas = np.min(A[i] + A[j])

            if A[i][j] > bipas:
                print(-1)
                return 0
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
a = [list(map(int,input().split())) for i in range(n)]

ans = 0
for i in range(n):
  ans += sum(a[i])

memo = {}
for i in range(n):
  memo[i] = {}
for k in range(n):
  for i in range(n):
    for j in range(n):
      if k != i and i != j and j != k :
        if a[i][j] > a[i][k]+a[k][j]:
          print(-1)
          exit()
        elif a[i][j] == a[i][k]+a[k][j]:
          if j not in memo[i]:
            ans -= a[i][j]
            memo[i][j] = 1
                  
print(ans//2)

Solution (Python):

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,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)
"""


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)

Solution (Python):

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,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)
"""


n = I()
a = LIR(n)
d = [[a[i][j] for i in range(n)] for j in range(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]:
                d[i][j] = d[i][k]+d[k][j]
                l[i][j] = l[i][k]+l[k][j]

if a != d:
    print(-1)
    quit()
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)

Solution (Python):
def main():
    N = int(input())
    A = [list(map(int, input().split())) for _ in range(N)]
    ans = 0
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            direct = True
            for k in range(N):
                if i == k or j == k:
                    continue
                if A[i][j] > A[i][k] + A[k][j]:
                    print(-1)
                    return
                if A[i][j] == A[i][k] + A[k][j] and i != k and j != k:
                    direct = False
            if direct:
                ans += A[i][j]
    print(ans // 2)


if __name__ == "__main__":
    main()

Solution (Python):
N=int(input())
inf=float("inf")
A=[list(map(int,input().split())) for _ in range(N)]

def calc():
    ans=sum(map(sum,A))
    for i in range(N):
        for j in range(N):
            used=True
            for k in range(N):
                if i==k or k==j:continue
                if A[i][j]>A[i][k]+A[k][j]:
                    return -1
                elif A[i][j]==A[i][k]+A[k][j]:
                    used=False
            if not used:
                ans-=A[i][j]
    return ans//2
                
print(calc())

Solution (Python):
N=int(input())
inf=float("inf")
A=[list(map(int,input().split())) for _ in range(N)]

def calc():
    ans=0
    for i in range(N):
        for j in range(N):
            used=True
            for k in range(N):
                if i==k or k==j:continue
                if A[i][j]>A[i][k]+A[k][j]:
                    return -1
                elif A[i][j]==A[i][k]+A[k][j]:
                    used=False
            if used:
                ans+=A[i][j]
    return ans//2
                
print(calc())

Solution (Python):
N=int(input())
inf=float("inf")
A=[list(map(int,input().split())) for _ in range(N)]

def calc():
    ans=0
    for i in range(N):
        for j in range(N):
            used=True
            for k in range(N):
                if A[i][j]>A[i][k]+A[k][j]:
                    return -1
                if i==k or k==j:continue
                if A[i][j]==A[i][k]+A[k][j]:
                    used=False
            if used:
                ans+=A[i][j]
    return ans//2
                
print(calc())

Solution (Python):
import heapq
N = int( input())
A = [ list( map( int, input().split())) for _ in range(N)]
Q = []
for i in range(N-1):
    for j in range(i+1,N):
        heapq.heappush(Q, [A[i][j],i,j])
WF = [ [10**9+1]*N for _ in range(N)]
for i in range(N):
    WF[i][i] = 0
cnt = 0
while Q:
    a, s, g = heapq.heappop(Q)
    addcheck = 1
    for i in range(N):
        if i == s or i == g:
            continue
        else:
            if WF[s][i] + WF[i][g] == a:
                addcheck = 0
            elif WF[s][i] + WF[i][g] < a:
                 break
    else:
        WF[s][g] = a
        WF[g][s] = a
        if addcheck:
            cnt += a
        continue
    print(-1)
    break
else:
    print( cnt)

Solution (Python):
INF = 10 ** 20
n = int(input())
edges = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * n for _ in range(n)]

edgeList = []
for i in range(n):
    for j in range(i, n):
        edgeList.append((edges[i][j], i, j))
edgeList.sort()

for k in range(n):
    edgesk = edges[k]
    for i in range(n):
        disti = dist[i]
        edgesik = edges[i][k]
        for j in range(n):
            if disti[j] > edgesik + edgesk[j]:
                disti[j] = edgesik + edgesk[j]

ans = 0
for c, i, j in edgeList:
    minCost = INF
    for k in range(n):
        if k in (i, j):continue
        if minCost > dist[i][k] + dist[k][j]:
            minCost = dist[i][k] + dist[k][j]
    if c > minCost:
        print(-1)
        break
    if c < minCost:
        ans += c
else:
    print(ans)

Solution (Python):


n = int(input())

a = []

for i in range(n):
    a_list = list(map(int, input().split()))
    a_dict = {i:e for i,e in enumerate(a_list[:i])}
    a.append(a_dict)

if n == 1:
    print("-1")
    exit()

elif n == 2:
    print(a[1][0])
    exit()


min_total = 0

for i in range(n):
    dim = i+1
    if dim == 1:
        continue
    elif dim == 2:
        min_total += a[1][0]
        continue

    paths_to_subgraph = []
    a_sorted = sorted(a[i].items(), key=lambda e:e[1])

    dest, path = a_sorted.pop(0)
    paths_to_subgraph.append((dest, path))
    min_total += path

    for dest, path in a_sorted:
        create_path = True
        for detour in paths_to_subgraph:
            detour_path = detour[1] + a[max([dest,detour[0]])][min([dest,detour[0]])]
            if path > detour_path:
                print("-1")
                exit()
            elif path == detour_path:
                create_path = False

        if create_path:
            for detour in paths_to_subgraph:
                detour_path = detour[1] + path
                minpath = a[max([dest,detour[0]])][min([dest,detour[0]])]
                if minpath > detour_path:
                    print("-1")
                    exit()
                elif minpath == detour_path:
                  
                  min_total -= minpath
            paths_to_subgraph.append((dest, path))
            min_total += path

print(min_total)

Solution (Python):
import copy
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
B = copy.deepcopy(A)

for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][k] + A[k][j] < A[i][j]:
                A[i][j] = A[i][k] + A[k][j]

flag = True
for i in range(N):
    for j in range(N):
        if A[i][j] != B[i][j]:
            flag = False
            break
    if not flag:
        break

if not flag:
    print(-1)
    exit()


for i in range(N):
    for j in range(N):
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][k] + A[k][j] == A[i][j]:
                B[i][j] = 0
print(sum(map(sum, B))//2)

Solution (Python):


from copy import deepcopy

N = int(input())
A = []
for i in range(N):
    A.append(list(map(int, input().split())))


B = deepcopy(A)
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]:
                print(-1)
                exit()
            
            elif A[i][j] == A[i][k] + A[k][j] and j != k and i != k and i < j:
                
                B[i][j] = 0


sm = 0
for i in range(N):
    for j in range(i+1, N):
        sm += B[i][j]
print(sm)

Solution (Python):
INF = 10 ** 12

N = int(input())
a = [list(map(int, 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)
                exit()

res = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i != k and j != k and a[i][j] == a[i][k] + a[k][j]:
                break
        else:
            res += a[i][j]

print(res)

Solution (Python):
N = int(input())
A = [list(map(int, input().split())) for i 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]:
                
                print(-1)
                exit()

ans = sum([sum(a) for a in A])
for i in range(N):
    for j in range(N):
        for k in range(N):  
            if i == k or k == j:
                continue

            if A[i][j] == A[i][k] + A[k][j]:
                
                ans -= A[i][j]
                break

print(ans // 2)

Solution (Python):
N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
w_graph = floyd_warshall(graph, directed=False)
for i in range(N):
    w_graph[i][i] = float("inf")
result = 0
for i in range(N):
     w_graph[i][i] = float("inf")
for i in range(N):
    for j in range(i):
        if w_graph[i][j] != graph[i][j]:
            print(-1)
            exit()
        if w_graph[i][j] < np.min(w_graph[i] + w_graph[j]):
            result += w_graph[i][j]
print(int(result))

Solution (Python):
N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
w_graph = floyd_warshall(graph, directed=False)
for i in range(N):
    w_graph[i][i] = float("inf")
result = 0
for i in range(N):
     w_graph[i][i] = float("inf")
for i in range(N):
    for j in range(i):
        if w_graph[i][j] != graph[i][j]:
            print(-1)
            exit()
        if w_graph[i][j] < np.min(w_graph[i] + w_graph[j]):
            result += w_graph[i][j]
print(int(result))

Solution (Python):
def warshall_floyd(graph):
    num_v = len(graph)

    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph

N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]


import numpy as np
from scipy.sparse.csgraph import floyd_warshall
w_graph = floyd_warshall(graph, directed=False)
result = 0
for i in range(N):
     w_graph[i][i] = float("inf")
for i in range(N):
    for j in range(i):
        if i == j:
            continue
        if w_graph[i][j] != graph[i][j]:
            print(-1)
            exit()
        if w_graph[i][j] < np.min(w_graph[i] + w_graph[j]):
            result += w_graph[i][j]
print(int(result))

Solution (Python):
def warshall_floyd(graph):
    num_v = len(graph)

    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph

N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
import copy
a_list = copy.deepcopy(graph)
w_graph = warshall_floyd(graph)
result = 0
for i in range(N):
    for j in range(i+1, N):
        if i == j:
            continue
        if w_graph[i][j] != a_list[i][j]:
            print(-1)
            exit()
        d = []
        for k in range(N):
            d.append(w_graph[i][k] + w_graph[j][k])
        if min(d) > w_graph[i][j]:
            result += w_graph[i][j]
print(result)

Solution (Python):
import heapq
N = int(input())
A = [[] for i in range(N)]
Q = []
for i in range(N):
  A[i] = [int(x) for x in input().split()]
  for j in range(i + 1, N):
    heapq.heappush(Q, [A[i][j], i, j])
G = [[10 ** 9 + 1 for j in range(N)] for i in range(N)]
for i in range(N):
  G[i][i] = 0
cnt = 0
while Q:
  [d, s, t] = heapq.heappop(Q)
  add = True
  for k in range(N):
    if d > G[s][k] + G[k][t]:
      break
    if d == G[s][k] + G[k][t]:
      add = False
  else:
    G[s][t] = d
    G[t][s] = d
    cnt += d if add else 0
    continue
  print(-1)
  break
else:
  print(cnt)

Solution (Python):
N = int(input())
A = [[] for i in range(N)]
for i in range(N):
    a = list(map(int, input().split()))
    A[i] = a


num = 0

for i in range(N):
    for j in range(i + 1, N):
        flag = True
        for k in range(N):
            if i == k or k == j:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                exit()
            elif A[i][j] == A[i][k] + A[k][j]:
                flag = False

        if flag:
            num += A[i][j]

print(num)

Solution (Python):
N = int(input())
A = [list(map(int,input().split())) for i in range(N)]

from scipy.sparse.csgraph import floyd_warshall as fw
import numpy as np
a = fw(A)
ans = 0
for i in range(N):
    a[i][i] = np.inf
for i in range(N):
    for j in range(i):
        if A[i][j]!=a[i][j]:
            print(-1)
            exit()
        else:
            if a[i][j] < np.min(a[i]+a[j]):
                ans += a[i][j]
print(int(ans))

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]

INF = float('inf')
graph = [[INF for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        graph[i][j] = a[i][j]

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(n):
    for j in range(n):
        if graph[i][j] < a[i][j]:
            print(-1)
            exit()

ans = 0

for i in range(n):
    for j in range(i+1, n):
        v = INF
        for k in range(n):
            if k == i or k == j:
                continue
            v = min(v, graph[i][k] + graph[k][j])
        if v != graph[i][j]:
            ans += graph[i][j]

print(ans)

Solution (Python):
import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

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

n = ni()
g = np.zeros((n,n))
for i in range(n):
    g[i,:] = np.array(list(li()))
    
    
dist = floyd_warshall(g, directed=False)

consis = True
for i in range(n):
    for j in range(n):
        if g[i,j] != dist[i,j]:
            consis = False
            break
        
if not consis:
    print(-1)
    
else:
    total = 0
    INF = float("inf")
    
    for i in range(n):
        dist[i,i] = INF
        
    for i in range(n):
        for j in range(i+1,n):
            via_k = np.min(dist[i] + dist[j])
            
            if via_k > dist[i,j]:
                total += dist[i,j]
                
    print(int(total))

Solution (Python):
N = int(input())
src = [list(map(int,input().split())) for i in range(N)]

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if src[i][j] > src[i][k] + src[k][j]:
                print(-1)
                exit()

for i in range(N-1):
    for j in range(i+1,N):
        for k in range(N):
            if k==i or k==j: continue
            if src[i][j] == src[i][k] + src[k][j]:
                break
        else:
            ans += src[i][j]
print(ans)

Solution (Python):
N = int(input())
src = [list(map(int,input().split())) for i in range(N)]

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if src[i][j] > src[i][k] + src[k][j]:
                print(-1)
                exit()

for i in range(N-1):
    for j in range(i+1,N):
        use = True
        for k in range(N):
            if k==i or k==j: continue
            if src[i][j] == src[i][k] + src[k][j]:
                use = False
                break
        if use:
            ans += src[i][j]
print(ans)

Solution (Python):
N = int(input())
src = [list(map(int,input().split())) for i in range(N)]

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if src[i][j] > src[i][k] + src[k][j]:
                print(-1)
                exit()
            src[i][j] = min(src[i][j], src[i][k] + src[k][j])

for i in range(N-1):
    for j in range(i+1,N):
        use = True
        for k in range(N):
            if k==i or k==j: continue
            if src[i][j] == src[i][k] + src[k][j]:
                use = False
                break
        if use:
            ans += src[i][j]
print(ans)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
INF = 10**9

n = int(input())
a = np.array([list(map(int, input().split())) for _ in range(n)])
a_opt = floyd_warshall(a)


for i in range(n):
    a[i][i] = INF
    
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if a_opt[i][j] < a[i][j]:
            print(-1)
            exit()
        else:
            d = a[i][j]
            if d < np.min(a[i]+a[j]):
                ans += d
                
            
            
            
            
            
            
            
print(ans)

Solution (Python):
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
n = int(input())
a = np.array([[int(i) for i in input().split()] for i in range(n)])
d,ans = floyd_warshall(a,directed=False),0
if any(a[i][j]!=d[i][j] for i in range(n) for j in range(n)): ans = -1
else:
	inf = 10**10
	for i in range(n): a[i][i] = inf
	for i in range(n):
		for j in range(i+1,n):
			num = np.min(a[i]+a[j])
			if num>a[i][j]: ans+=a[i][j]
print(int(ans))

Solution (Python):
import numpy as np
n=int(input())
l=[np.array(input().split(), dtype=np.int64) for _ in [0]*n]
l+=np.diag([10**10]*n)

v=0
for i in range(n-1):
  for j,d1 in enumerate(l[i][i+1:]):
    d2=np.min(l[i]+l[j+i+1])
    if d1>=d2:
      if d1>d2:
        print(-1)
        exit()
    else:
      v+=d1
print(v)

Solution (Python):
n=int(input())
l=[list(map(int,input().split()))    for _ in range(n)]

def chk():
  v=0
  for j in range(n):
    for i in range(n):
      f=True
      for k in range(n):
        if l[i][j]>l[i][k]+l[k][j]:
          return -1
        if l[i][j]==l[i][k]+l[k][j] and i!=k and k!=j:
          f=False
      if f:v+=l[i][j]
  return v//2
print(chk())

Solution (Python):
from scipy.sparse.csgraph import floyd_warshall
import numpy as np
import sys
sdin = sys.stdin.readline

n = int(sdin())
graph = np.array([[0 for _ in range(n)] for _ in range(n)], dtype=float)
for i in range(n):
    graph[i] = np.array(list(map(int, sdin().split())))
    

shortest = floyd_warshall(graph, directed=False)


if any([graph[i,j] != shortest[i,j] for i in range(n) for j in range(n)]):
    print(-1)
    
else:
    total = 0
    INF = float("inf")
    
    for i in range(n):
        graph[i,i] = INF
    
    for i in range(n):
        for j in range(i+1,n):
            via_k = np.min(graph[i] + graph[j])
            
            if via_k > graph[i,j]:
                total += graph[i,j]
                
    print(int(total))

Solution (Python):
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
def Warshall_Floyd(edges,N):
  ans = 0
  for j in range(N):
    for i in range(N):
      flag = 0
      for k in range(N):
        if edges[i][j]> edges[i][k]+edges[k][j]:
          print(-1)
          exit()
        if (edges[i][k] + edges[k][j] == edges[i][j] and i != k and k != j):
          flag = 1
      if flag == 0:
        ans += edges[i][j]
  return edges,ans
x,ans = Warshall_Floyd(a,n)
print(ans//2)

Solution (Python):
N=int(input())
A=[[int(i) for i in input().split()] for i in range(N)]
ans=0
for i in range(N):
    for j in range(i+1,N):
        flag=True
        for k in range(N):
            if j==k or i==k:
                continue
            if A[i][j]>A[i][k]+A[k][j]:
                print(-1)
                exit()
            if A[i][j]==A[i][k]+A[k][j]:
                flag=False
        if flag:
            ans+=A[i][j]
print(ans)

Solution (Python):
from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
AtoZ = [chr(i) for i in range(65,65+26)]
atoz = [chr(i) for i in range(97,97+26)]

def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())


N = int(input())
lines = []

for i in range(N):
	lines.append(inpl())

ans = 0
for s in range(N):
	for t in range(s+1,N):
		c = lines[s][t]
		ans += c
		for mid in range(N):
			if mid == s or mid == t:
				continue
			a = lines[s][mid]
			b = lines[mid][t]
			if a+b < c:
				print(-1)
				sys.exit()
			elif a+b == c:
				ans -= c
				break
print(ans)

Solution (Python):
from sys import exit
n = input()
arr = []
for i in range(n):
	t = map(int,raw_input().split())
	arr.append(t)
ans = 0
for i in range(n):
	for j in range(n):
		flag = False
		for k in range(n):
			if k == j or k == i:
				continue
			elif arr[i][k]+arr[k][j] < arr[i][j]:
				print "-1"
				exit(0)
			elif arr[i][k]+arr[k][j] == arr[i][j]:
				flag = True
				continue
		if flag == False:
			ans += arr[i][j]
print ans//2