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 copy import deepcopy
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
B = deepcopy(A)

s = 0
for i in range(N):
    via = A[i]
    for j in range(N):
        start = A[j]
        for k in range(N):
            if start[k] > start[i]+via[k]:
                print(-1)
                exit()

for j in range(N):
    for k in range(j):
        a = A[j][k]
        for i in range(N):
            if i in {j, k}:
                continue
            if a == A[j][i]+A[i][k]:
                break
        else:
            s += a
            
print(s)

Solution (Python):
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
import sys

n = ni()
cost =[]
tot = 0
for i in range(n):
    A = lma()
    cost.append(A)
    tot+=sum(A)
nu=[[False]*n for i in range(n)]
for k in range(n):
    for i in range(n):
        if i==k:continue
        for j in range(n):
            if j==k:
                continue
            
            if cost[i][j] >cost[i][k] + cost[k][j]:
                print(-1)
                exit()
            elif cost[i][j]==cost[i][k] + cost[k][j]:

                nu[i][j]=True

for i in range(n):
    for j in range(n):
        if nu[i][j]:
            tot-=cost[i][j]
print(tot//2)

Solution (Python):
N = int(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)

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




f = 0
r = [[1] * N 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]:
                f = 1
            elif A[i][j] == A[i][k] + A[k][j] and i != k and j != k:
                r[i][j] = 0

if f == 1:
    print("-1")
else:
    
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += A[i][j] * r[i][j]

    print(ans)

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

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

answer = 0
for i in range(N):
    for j in range(i+1, N):
  
        count = INF
        for k in range(N):   
            count = min(count, A[i][k] + A[k][j])
        
        if A[i][j] > count:
            print(-1)
            exit()

        if A[i][j] < count:
            answer += A[i][j]
        
print(answer)

Solution (Python):
INF = 10**18

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


dist = [G[i][:] for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

ans = 0
for i in range(N):
    for j in range(i+1,N):
        ans += G[i][j]

        if dist[i][j] < G[i][j]:
            print(-1)
            exit()

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

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

e=[[True]*N for _ in range(N)]
ans=0
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][k]!= 0) and (A[k][j]!= 0):
        e[i][j]=False

ans=0
for i in range(N):
  for j in range(N):
    if e[i][j]: ans+=A[i][j]

print(ans//2)

Solution (Python):
import sys
import copy

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


INF = 10**18


def warshall_floyd(V, cost):
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if cost[i][k] < INF and cost[k][j] < INF:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])


def main():

    V = in_n()
    cost = [[] for _ in range(V)]

    for i in range(V):
        cost[i] = in_nl()

    short_cost = copy.deepcopy(cost)
    warshall_floyd(V, short_cost)

    ans = 0
    for i in range(V):
        for j in range(i + 1, V):
            if short_cost[i][j] < cost[i][j]:
                print(-1)
                exit()
            for k in range(V):
                if i == k or j == k:
                    continue
                if short_cost[i][k] + short_cost[k][j] == cost[i][j]:
                    break
            else:
                ans += cost[i][j]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):


import sys

N = int(input())
A = []
for _ in range(N):
    a = list(map(int, sys.stdin.readline().strip().split()))
    b = a
    A.append(a)

needless = [[False] * 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]:
                print(-1)
                sys.exit()
            elif (A[i][j] == A[i][k] + A[k][j]) and (A[i][k] != 0) and (A[k][j] != 0):
                needless[i][j] = True




ans = 0
for h in range(N):
    for w in range(N):
        if needless[h][w] is False:
            ans += A[h][w]

print(ans // 2)

Solution (Python):
from itertools import product
def main(): 
    with open(0) as f:
        N = int(f.readline())
        A = [list(map(int, line.split())) for line in f.readlines()]

    possible = True
    ans = 0
    r = range(N)
    for i,j in product(r, r) :
        if j <= i: continue
        for k in r:
            if k == i or k == j:
                continue
            if A[i][j] < A[i][k] + A[k][j]:
                continue
            elif A[i][j] == A[i][k] + A[k][j]:
                break
            else:
                possible = False
            break
        else:
            ans += A[i][j]
    print(ans if possible else -1)


if __name__ == '__main__':
    main()

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

    for i in r: A[i][i] = float('inf')
    possible = True
    ans = 0
    for i in r :
        for j in range(i+1,N):
            for k in r:
                if A[i][j] < A[i][k] + A[k][j]:
                    continue
                elif A[i][j] == A[i][k] + A[k][j]:
                    break
                else:
                    possible = False
                    break
            else:
                ans += A[i][j]
    print(ans if possible else -1)

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Solution (Python):
import sys
import copy
n = int(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]:
                
                e[i][j]=float("inf")


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)

Solution (Python):
from collections import deque
import sys, copy, itertools,heapq
input = sys.stdin.readline

n = int(input())
MAP = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  MAP[i][i]=10**9


ans = 0
for i in range(n):
  for j in range(i+1,n):
    MAPP=[0]*n
    for k in range(n):
      MAPP[k]=MAP[i][k]+MAP[j][k]
    d = min(MAPP)
    if MAP[i][j] < d:
      ans += MAP[i][j]
    elif d < MAP[i][j]:
      print(-1)
      exit()
  

print(ans)

Solution (Python):
n=int(input())
inf=10**15
a=[[0]*n for _ in range(n)]
dist=[[0]*n for _ in range(n)]

for u in range(n):
    for v,c in enumerate(list(map(int,input().split()))):
        a[u][v]=c
        dist[u][v]=c

def calc(n,a,dist):

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if k==i or k==j or i==j or dist[i][k]==inf or dist[k][j]==inf:
                    continue
                
                if dist[i][k]+dist[k][j]==a[i][j]:
                    dist[i][j]=inf
                elif dist[i][k]+dist[k][j]<a[i][j]:
                    return -1
    
    ret=0
    for i in range(n):
        for j in range(n):
            if dist[i][j]==inf:
                continue
            ret+=dist[i][j]
    
    return ret//2


print(calc(n,a,dist))

Solution (Python):
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    A = [LI() for i in range(N)]

    dq = []
    heapify(dq)
    
    for i in range(N):
        for j in range(N):
            heappush(dq, (A[i][j], i, j))
    
    
    dist = [[float('inf') if i != j else 0 for i in range(N)] for j in range(N)]
    
    res = 0
    
    while dq:
        d, x, y = heappop(dq)
        equal = True
        for i in range(N):
            tempD = dist[x][i]+dist[i][y]
            if d > tempD:
                print(-1)
                exit()
            elif d == tempD:
                equal = False
    
        dist[x][y] = d
        dist[y][x] = d
    
        if equal:
            res+=d

    print(res)

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]

    for i in range(n):
        alst[i][i]=inf

    sm=0
    token=0

    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1

    print(sm)

main()

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

d = [[A[i][j] for i in range(N)]for j in range(N)]

for k in range(N):
    for i in range(N):
        for j in range(N):
            d[i][j] = min(d[i][j],d[i][k]+d[k][j])

for i in range(N):
    for j in range(N):
        if A[i][j]!=d[i][j]:
            print(-1)
            exit()

ans = 0

for i in range(N):
    for j in range(N):
        ok = True
        for k in range(N):
            if k == i or k == j:
                continue
            if d[i][j]==d[i][k]+d[j][k]:
                ok=False
        if ok:
            ans+=d[i][j]

print(ans//2)

Solution (Python):
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
INF = 10**9 + 1
dp = [[INF]*n for _ in range(n)]


for i, line in enumerate(A):
    for j, a in enumerate(line):
        dp[i][j] = a

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        d = dp[i][j]
        if d < A[i][j]:
            ans = -1
            break
        else:
            for k in range(n):
                if k == i or k == j:
                    continue
                if dp[i][k] + dp[k][j] == d:
                    break
            else:
                ans += d
    if ans == -1:
        break
print(ans)

Solution (Python):
from copy import deepcopy
import sys
input = sys.stdin.readline


def warshall_floyd(d):
    
    
    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]


def check(a, b):
    res = 0
    for i in range(n):
        for j in range(i + 1, n):
            if b[i][j] < a[i][j]:
                return -1
            flag = True
            for k in range(n):
                if k == i or k == j:
                    continue
                if b[i][j] == b[i][k] + b[k][j]:
                    flag = False
                    break
            if flag:
                res += a[i][j]
    return res


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
b = deepcopy(a)
warshall_floyd(b)
ans = check(a, b)
print(ans)

Solution (Python):
def main():
    from sys import stdin
    input = stdin.readline

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

    ans = 0
    tf = [[True] * n for _ in range(n)]
    
    for k in range(n):
        for i in range(n-1):
            if i == k:
                continue
            for j in range(i, n):
                if j == k:
                    continue
                elif a[i][j] > a[i][k] + a[k][j]:
                    print(-1)
                    exit()
                elif a[i][j] == a[i][k] + a[k][j] and tf[i][j]:
                    ans -= a[i][j]
                    tf[i][j] = False
    
    ans += sum([sum(i) for i in a]) // 2
    print(ans)

main()

Solution (Python):
def main():
    from sys import stdin
    input = stdin.readline

    n = int(input())
    a = []
    for _ in range(n):
        a.append(list(map(int, input().split())))
    
    ans = 0
    tf = [[True] * n for _ in range(n)]
    
    for k in range(n):
        for i in range(n-1):
            if i == k:
                continue
            for j in range(i, n):
                if j == k:
                    continue
                elif a[i][j] > a[i][k] + a[k][j]:
                    print(-1)
                    exit()
                elif a[i][j] == a[i][k] + a[k][j] and tf[i][j]:
                    ans -= a[i][j]
                    tf[i][j] = False
    
    ans += sum([sum(i) for i in a]) // 2
    print(ans)

main()

Solution (Python):
import sys
import copy

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

def fnc(M):
    m = list([True]*len(M) for _ in range(len(M)))
    for k in range(len(M)):
        for i in range(len(M)):
            for j in range(len(M)):
                if M[i][j] > M[i][k]+M[k][j]:
                    print(-1)
                    sys.exit()
                if M[i][j] == M[i][k]+M[k][j] and i != k and j != k:
                    m[i][j] = False
    return M,m

M,m = fnc(A)

ans = 0
for i in range(N):
    for j in range(N):
        if m[i][j]:
            ans += M[i][j]
        
print(ans//2)

Solution (Python):
import sys
input = sys.stdin.readline
if __name__ == "__main__":
    N = int(input())
    V = N
    dp = []
    for i in range(N):
        dp.append(list(map(int,input().split())))
    edge = [[True]*N for _ in range(N)]
    for k in range(V):
        for i in range(V):
            for j in range(V):
                a = dp[i][j]
                b = dp[i][k]+dp[k][j]
                if a > b:
                    print(-1)
                    exit(0)
                elif a == b and k != i and k != j:
                    edge[i][j] = False
                    edge[j][i] = False
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            if edge[i][j]:
                ans += dp[i][j]
    print(ans)

Solution (Python):

import sys 
from heapq import heappop,heappush
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())

cost = [[0]*(N+1) for _ in range(N+1)] 
tmp = [[0]*(N+1) for _ in range(N+1)] 
for i in range(N):
    A = list(map(int,readline().split()))
    for j in range(N):
        cost[i+1][j+1] = A[j]
        tmp[i+1][j+1] = A[j]
        

for k in range(1,N+1):
    for i in range(1,N+1):
        for j in range(1,N+1):
            if cost[i][j] > cost[i][k] + cost[k][j]:
                print(-1)
                sys.exit()
            if cost[i][k] and cost[k][j] and cost[i][j] == cost[i][k] + cost[k][j]:
                tmp[i][j] = 0

ans = sum([sum([c for c in row]) for row in tmp])
print(ans//2)

Solution (Python):
import numpy as np
N = int(input())
A = np.array([input().split() for _ in range(N)], dtype=np.int64)

np.fill_diagonal(A, 10**9)

ans = 0
for i in range(N):
  for j in range(i+1,N):
    d = np.min(A[i]+A[j])
    if A[i][j] < d:
      ans += A[i][j]
    elif d < A[i][j]:
      print(-1)
      exit()

print(ans)

Solution (Python):
from numpy import *
N = int(input())
A = array([input().split() for _ in range(N)], dtype=int64).reshape(N,N)

fill_diagonal(A, 10**9)

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

print(ans)

Solution (Python):
from numpy import *
N = int(input())
A = array([input().split() for _ in range(N)], dtype=int64)

fill_diagonal(A, 10**9)

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

print(ans)

Solution (Python):
from numpy import *
N = int(input())
A = array([input().split() for _ in range(N)], dtype=int64)

fill_diagonal(A, 10**10)

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

print(ans)

Solution (Python):
from numpy import *
N = int(input())
A = array([list(map(int,input().split())) for n in range(N)])

fill_diagonal(A, 10**10)

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

print(ans)

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

def warshall_floyd(adj_mat: list):
    """
    ワーシャルフロイド
    隣接行列を受け取る(隣接していないノードはINF、自身へのコストは0)
    全点の間の最短距離をあらわす行列を返す(V * V)
    O(|V|**3)
    ネスト深くならないバージョン
    """
    mat = adj_mat.copy()
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if mat[i][j] > mat[i][k] + mat[k][j]:
                    return -1
                elif mat[i][j] == mat[i][k] + mat[k][j] and i != k and k != j:
                    is_need[i][j] = 0
                
    return mat

adj = warshall_floyd(A)
if adj == -1:
    print(-1)
else:
    ans = 0
    for i in range(N):
        for j in range(N):
            if is_need[i][j]:
                ans += A[i][j]
    print(ans//2)

Solution (Python):
import copy

n = int(input())
a = []
for i in range(n):
    a.append(list(map(int, input().split())))
dis = copy.deepcopy(a)

def warshall_floyd(dis):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j])
    return dis

data = warshall_floyd(dis)
flag = True
for i in range(n):
    for j in range(i + 1, n):
        if data[i][j] < a[i][j]:
            flag = False
            break
    if flag == False:
        break
if flag == False:
    print(-1)
else:
    count = 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 data[i][k] + data[k][j] == data[i][j]:
                    break
            else:
                count += data[i][j]
    print(count)

Solution (Python):
from numpy import *
N = int(input())
A = array([list(map(int,input().split())) for n in range(N)])
ans = 0

for n in range(N):
  A[n][n] = 10**9

for i in range(N):
  for j in range(i+1,N):
    dp = min(A[i]+A[j])
    if A[i][j]<dp:
      ans+=A[i][j]
    elif dp<A[i][j]:
      print(-1)
      exit()

print(ans)

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

N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
A2 = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        A2[i][j] = A[i][j]
for k in range(N):
    for i in range(N):
        for j in range(N):
            A2[i][j] = min(A2[i][j], A2[i][k]+A2[k][j])
ok = True
for i in range(N):
    for j in range(N):
        if A[i][j] != A2[i][j]:
            ok = False
if not ok:
    print(-1)
    exit()
ans = 0
for i in range(N):
    for j in range(N):
        connected = True
        for k in range(N):
            if i == k or j == k: continue
            if A[i][j] == A[i][k]+A[k][j]:
                connected = False
                break
        if connected:
            ans += A[i][j]
print(ans//2)

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 = 0
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 A[i][j] == A[i][k] + A[k][j]:
                break
        else:
            ans += A[i][j]
print(ans)

Solution (Python):
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD

def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD

def fact_and_inv(SIZE):
    inv = [0] * SIZE  
    fac = [0] * SIZE  
    finv = [0] * SIZE  
    inv[1] = 1
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    for i in range(2, SIZE):
        inv[i] = MOD - (MOD // i) * inv[MOD % i] % MOD
        fac[i] = fac[i - 1] * i % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

    return fac, finv

def renritsu(A, Y):
    
    
    
    A = np.matrix(A)
    Y = np.matrix(Y)
    Y = np.reshape(Y, (-1, 1))
    X = np.linalg.solve(A, Y)

    
    return X.flatten().tolist()[0]

class TwoDimGrid:
    
    def __init__(self, h, w, wall="
        self.h = h
        self.w = w
        self.size = (h+2) * (w+2)
        self.wall = wall
        self.get_grid()
        

    def get_grid(self):
        grid = [self.wall * (self.w + 2)]
        for i in range(self.h):
            grid.append(self.wall + getS() + self.wall)

        grid.append(self.wall * (self.w + 2))
        self.grid = grid
    def init_cost(self):
        self.cost = [INF] * self.size

    def pos(self, x, y):
        
        return y * (self.w + 2) + x
    def getgrid(self, x, y):
        return self.grid[y][x]
    def get(self, x, y):
        return self.cost[self.pos(x, y)]
    def set(self, x, y, v):
        self.cost[self.pos(x, y)] = v
        return
    def show(self):
        for i in range(self.h+2):
            print(self.cost[(self.w + 2) * i:(self.w + 2) * (i+1)])
    def showsome(self, tgt):
        for t in tgt:
            print(t)
        return
    def showsomejoin(self, tgt):
        for t in tgt:
            print("".join(t))
        return

    def search(self):
        grid = self.grid
        move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        move_eight = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        
        
        
        
        

def solve():
    n = getN()
    g = []
    for i in range(n):
        g.append(getList())

    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            cc = g[i][j]
            fl = True
            for k in range(n):
                if k == i or k == j:
                    continue
                if g[i][k] + g[j][k] < cc:
                    print(-1)
                    return
                elif g[i][k] + g[j][k] == cc:
                    fl = False

            if fl:
                ans += cc

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    A = [list(map(int, input().split())) for _ in range(n)]
    flg = [[True] * n for _ in range(n)]

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

    res = 0
    for i in range(n):
        for j in range(n):
            if flg[i][j]:
                res += A[i][j]

    print(res // 2)


if __name__ == '__main__':
    resolve()

Solution (Python):
import copy

n=int(input())
a=[]
ans=0
for _ in range(n):
  b=list(map(int,input().split()))
  ans+=sum(b)
  a.append(b)
  
c=copy.deepcopy(a)
  
for i in range(n):
  for j in range(n):
    ch=0
    for k in range(n):
      if c[i][j]==c[i][k]+c[k][j] and ch==0 and i!=k and j!=k:
        ans-=c[i][j]
        ch+=1
      c[i][j]=min(c[i][j],c[i][k]+c[k][j])
      
if a==c:
  
  print(ans//2)
  
else:
  print(-1)

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

total = 0
for i in range(n-1):
    for j in range(i+1,n):
        flg = True
        for x in range(n):
            if x == i or x == j:
                continue
            if a[i][j] > a[i][x] + a[j][x]:
                print(-1)
                exit()
            elif a[i][j] == a[i][x] + a[j][x]:
                flg = False
                break
        if flg:
            total += a[i][j]
            
print(total)

Solution (Python):
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict


input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  
  
from functools import lru_cache





n=int(input())
A=[]

for i in range(n):
    a=list(map(int,input().split()))
    A.append(a)
    


miti=[[] for i in range(n)]
for i in range(n):
    miti[i]=A[i][:]
    
for k in range(n):
    for j in range(k):
        for i in range(j):
            q=A[i][j]
            w=A[j][k]
            e=A[k][i]
            
            
            
            if q+w==e and q!=inf and w!=inf: miti[k][i]=inf;miti[i][k]=inf;continue
            if q+w<A[k][i] and q!=inf and w!=inf: print(-1);exit()
            if w+e==q and e!=inf and w!=inf: miti[i][j]=inf;miti[j][i]=inf;continue
            if w+e<A[i][j]  and e!=inf and w!=inf : print(-1);exit()
            if e+q==A[j][k] and q!=inf and e!=inf: miti[j][k]=inf;miti[k][j]=inf;continue
            if e+q<A[j][k] and q!=inf and e!=inf: print(-1);exit()
            
            
                
            
ans=0
for i in range(n):
    for j in range(n):
        if miti[i][j]!=inf:
            ans+=miti[i][j]

print(ans//2)