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):
n=int(input())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))

s=[]
for i in range(n):
  for j in range(i+1,n):
    s.append((a[i][j],i,j))
s.sort()

c=0
for i in s:
  mn=10**10
  for j in range(n):
    if i[1]==j or i[2]==j:
      continue
    mn=min(mn,a[i[1]][j]+a[i[2]][j])
  if mn>a[i[1]][i[2]]:
    c+=a[i[1]][i[2]]
  elif mn<a[i[1]][i[2]]:
    c=-1
    break
print(c)

Solution (Python):







INF = float("inf")
import copy

def warshall_floyd(d):
    n = len(d)
    wf = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                wf[i][j] = min(wf[i][j], wf[i][k] + wf[k][j])

    return wf 



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

if d != warshall_floyd(d):
    print(-1)
else:
    ret = 0
    for i in range(n):
        for j in range(i+1,n):
            if i == j: continue
            ret += d[i][j]
            for mid in range(n):
                if mid in (i, j): continue
                if d[i][mid] + d[mid][j] == d[i][j]:
                    ret -= d[i][j]
                    break
    print(ret)

Solution (Python):
import itertools
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

N, *Z = [int(_) for _ in open(0).read().split()]
A = []
B = []
C = []
for z in range(N * N):
    x, y = divmod(z, N)
    A += [x]
    B += [y]
    C += [Z[z]]
G = csr_matrix((C, (A, B)), (N, N))
F = np.array(floyd_warshall(G, directed=1), dtype=np.int64)
Z = np.array(Z).reshape(N, N)
if np.all(F==Z):
    ans = np.sum(Z)
    for i, j in itertools.product(range(N), repeat=2):
        ans -= Z[i, j] * (np.sum(Z[i] + Z[j] == Z[i, j]) > 2)
    ans //= 2
    print(ans)
else:
    print(-1)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,read().split()))

rem = set()
ans = sum(a)//2
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            x = [a[i*n+j], a[i*n+k], a[j*n+k]]
            max_x = max(x)
            if(max_x == x[0]):
                ind = i*n+j
            elif(max_x == x[1]):
                ind = i*n+k
            else:
                ind = j*n+k
            x.sort()
            if(x[2] > x[0]+x[1]):
                print(-1)
                exit()
            elif(x[2] == x[0]+x[1]):
                rem.add(ind)

for i in rem:
    ans -= a[i]

print(ans)

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

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

def check(n,a):
    ans = 0
    ok = 1
    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 a[i][k] + a[j][k] < a[i][j]:
                    return -1
                elif a[i][k] + a[j][k] == a[i][j]:
                    break
            else:
                ans += a[i][j]
    return ans
            
print(check(n,a))

Solution (Python):
def WarshallFloyd(M):
    N = len(M)
    M = [m[:] for m in M]
    for k in range(N):
        for j in range(N):
            for i in range(N):
                M[i][j] = min(M[i][j], M[i][k] + M[k][j])
    return M

N, *A = map(int, open(0).read().split())
A = list(map(list, zip(*[iter(A)] * N)))

B = WarshallFloyd(A)

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if A[i][j] > B[i][j]:
            print(-1)
            quit()

        if A[i][j] == B[i][j] and all(B[i][j] != B[i][k] + B[k][j] for k in range(N) if k != i and k != j):
            ans += B[i][j]

print(ans)

Solution (Python):

import sys
input=sys.stdin.buffer.readline
n=int(input())
d=[list(map(int,input().split())) for _ in range(n) ]


for k in range(n):
    for i in range(n):
        for j in range(i+1,n):
            if d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
ans=0
for i in range(n):
    for j in range(i+1,n):
        flag=True
        for k in range(n):
            if k!=i and k!=j and d[i][k]+d[k][j]==d[i][j]:
                flag=False
        if flag:
            ans+=d[i][j]
print(ans)

Solution (Python):
import numpy as np
import scipy.sparse.csgraph as csg
n=int(input())
g=np.array([list(map(int,input().split())) for _ in range(n)],dtype=np.uint32)
g2=csg.floyd_warshall(g,directed=False)
if np.any(g!=g2):
  print(-1)
else:
  g[g==0]=2*10**9
  t=0
  for i in range(n):
    for j in range(i+1,n):
      m=np.min(g[i]+g[j])
      if m>g[i,j]:
        t+=g[i,j]
  print(t)

Solution (Python):
n = int(input())
d = [[10**16]*n for i in range(n)]
L = []
ans = 0
for i in range(n):
    d[i][i] = 0
for i in range(n):
    L = list(map(int,input().split()))
    for j in range(i+1):
        d[i][j] = L[j]
        d[j][i] = L[j]
        ans += L[j]
flag = True
for i in range(n):
  for j in range(i+1):
    for k in range(n):
      if d[i][j] > d[i][k]+d[k][j]:
        print(-1)
        exit()
      else:
        if d[i][j] == d[i][k]+d[k][j] and i != k and k != j:
          ans -= d[i][j]
          break
print(ans)

Solution (Python):
N, = map(int, input().split())
X = []
for _ in range(N):
    X.append(list(map(int, input().split())))
Y = []
for i in range(N):
    for j in range(i+1, N):
        Y.append((i, j, X[i][j]))

r = 0
for i, j, x in Y:
    mn = 10**18
    for k in range(N):
        if k == i or k == j:
            continue
        mn = min(mn, X[i][k] + X[j][k])
    if mn < x:
        r = -1
        break
    if mn > x:
        r += x
print(r)

Solution (Python):
"""
ワーシャルフロイド風に全探索で-1を炙り出す

条件を満たすとき:
A→Bの経路 == A→C→Bの経路
ならA→Bを合計から引く？
残るのは隣り合ったやつだけ？？

完全グラフから不要物を取り除いていく
A→C→B == A→Bだった場合、AB間は絶対に不要

"""

import sys

N = int(input())

A = []
s = 0

for i in range(N):
    a = list(map(int,input().split()))
    s += sum(a)
    A.append(a)

s //= 2


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()

for k in range(N):

    for i in range(N):
        for j in range(N):

            if i == j or i == k or j == k:
                continue
            if 0 in [ A[i][j] ,A[i][k] ,A[k][j]]:
                continue

            if A[i][j] == A[i][k] + A[k][j]:
                s -= A[i][j]
                A[i][j] = 0
                A[j][i] = 0
                
                

print (s)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def dijkstra(edge,st):
    
    
    n=len(edge)
    d=[(0 if st==i else inf,i) for i in range(n)]
    prev=[0]*n
    q=[i for i in d]
    heapify(q)
    
    
    while q:
        dist,cur=heappop(q)
        for dst,dist in edge[cur]:
            alt=d[cur][0]+dist
            if alt<d[dst][0]:
                d[dst]=(alt,dst)
                prev[dst]=cur
                heappush(q,(alt,dst))
    return d,prev
    
show_flg=False
show_flg=True

ans=0
n=I()
d=[]
c=[[1]*n for i in range(n)]
for i in range(n):
    d.append(LI())


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 d[i][k]+d[k][j]<d[i][j]:
                print(-1)
                exit()
            if d[i][k]+d[k][j]==d[i][j]:
                c[i][j]=0

for i in range(n):
    for j in range(i+1,n):
        ans+=d[i][j]*c[i][j]

    
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
def solve():
  n  = int(input())
  a = [list(int(i) for i in input().split()) for _ in range(n)]
  a2 = []
  
  for k in range(n):
    for i in range(n):
      for j in range(i+1,n):
        if not k in [i,j]:
         if a[i][j] > a[i][k] + a[k][j]:
          
           print(-1)
           exit()
         elif a[i][j] ==  a[i][k] + a[k][j]:
          a2.append((i,j))
  for i,j in a2:
    a[i][j] = 0
  ans = 0
  for i in range(n):
    for j in range(i+1,n):
        ans += a[i][j]
  print(ans)
solve()

Solution (Python):

def solve():
  n  = int(input())
  a = []
  for i in range(n):
    tp = list(int(i) for i in input().split())
    a.append(tp)
  a2 = []
  
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if not k in [i,j]:
         if a[i][j] > a[i][k] + a[k][j]:
          
           print(-1)
           exit()
         elif a[i][j] ==  a[i][k] + a[k][j]:
          a2.append((i,j))
  for i,j in a2:
    a[i][j] = 0
  ans = 0
  for i in range(n):
    for j in range(n):
      if i < j:
        ans += a[i][j]
  print(ans)
solve()

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict
import copy

INF = float("inf")


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

def build(d, n):
	cost = 0
	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] and k != i and k != j:
					d[i][j] = INF
				
	return d

def judge(d, 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])
	return d


def main():
	
	N = int(input())
	d = []
	for i in range(N):
		g = getlist()
		d.append(g)

	
	d2 = copy.deepcopy(d)
	d2 = judge(d2, N)

	if d != d2:
		print(-1)
	else:
		
		X = build(d2, N)
		ans = 0
		for i in range(N):
			for j in range(N):
				if d2[i][j] != INF:
					ans += d2[i][j]
		print(ans // 2)


if __name__ == '__main__':
	main()

Solution (Python):
import itertools
N = int(input())
A = [[int(_) for _ in input().split()] for _ in range(N)]
ans = sum(sum(a) for a in A) // 2
seen = set()
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if A[i][j] > A[i][k] + A[j][k]:
                print(-1)
                exit()
            elif k == i or i == j or j == k:
                continue
            elif A[i][j] == A[i][k] + A[j][k]:
                ans -= A[i][j]
                break
print(ans)

Solution (Python):
N = int(input())
A = [[] for _ in range(N)]

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

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):
    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):
def warshall_floyd(G):
    import copy
    ret = copy.deepcopy(G)
    for k in range(N):
        for i in range(N):
            for j in range(N):
                ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
    return ret


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

if A == warshall_floyd(A):
    ans = 0
    for i in range(1, N):
        for j in range(0, i):
            if min([A[i][k] + A[k][j] - A[i][j] for k in range(N) if k != i and k != j] + [1]) > 0:
                ans += A[i][j]
    print(ans)
else:
    print(-1)

Solution (Python):
n=int(input())
table=[]
for i in range(n):
  table.append([int(_) for _ in input().split()])
T=[[1]*n for i in range(n)]
import itertools
chk,ans=True,0
for Com in itertools.combinations(range(n),3):
  a,b,c=Com[0],Com[1],Com[2]
  lab,lbc,lca=table[a][b],table[b][c],table[c][a]
  if lab>=lbc and lab>=lca:
    if lab>lbc+lca:
      chk=False
    elif lab==lbc+lca:
      T[a][b],T[b][a]=0,0
  elif lbc>=lab and lbc>=lca:
    if lbc>lab+lca:
      chk=False
    elif lbc==lab+lca:
      T[b][c],T[c][b]=0,0
  elif lca>=lab and lca>=lbc:
    if lca>lab+lbc:
      chk=False
    elif lca==lab+lbc:
      T[c][a],T[a][c]=0,0
for i in range(n):
  for j in range(i+1,n):
    if T[i][j]==1:
      ans+=table[i][j]
print(ans if chk==True else -1)

Solution (Python):
import copy
N=int(input())

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

C=copy.deepcopy(A)
for c in range(N):
    for a in range(N):
        for b in range(N):
            if a!=b and a!=c and b!=c:
                if C[a][b]==(C[a][c]+C[c][b]):
                    B[a][b]=0
                    B[b][a]=0
                A[a][b]=min(A[a][b],A[a][c]+A[c][b])
if C==A:
    ans=0
    for i in range(N):
        for j in range(N):
            if B[i][j]==1:
                ans+=A[i][j]
    print(ans//2)
else:
    print(-1)

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

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

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

print(ans // 2)

Solution (Python):

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


ans = (
    -1 if any(
        A[u][v] > A[u][k] + A[k][v]
        for u in range(N)
        for v in range(u + 1, N)
        for k in range(N)
        if k != u and k != v
    ) else
    sum(sum(a) for a in A) // 2 - sum(
        A[u][v]
        for u in range(N)
        for v in range(u + 1, N)
        if any(
            A[u][v] == A[u][k] + A[k][v]
            for k in range(N)
            if k != u and k != v
        )
    )
)


print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

use = [[0]*N for _ in range(N)]

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]:
                print("-1")
                exit()
            if mat[i][j] == mat[i][k]+mat[k][j] and i != k and k != j:
                use[i][j] = 1
ans = 0
for i in range(N):
    for j in range(N):
        if use[i][j] == 0:
            ans += mat[i][j]
print(ans//2)

Solution (Python):
n = int(input())

amap = [list(map(int, input().split())) for _ in range(n)]
isnt_const = False
cost = 0
for i in range(n):
  for j in range(i+1, n):
    isnt_add = False
    for k in range(n):
      if i == k or k == j:
        continue
      if amap[i][j] > amap[i][k] + amap[k][j]:
        isnt_const = True
        break
      elif amap[i][j] == amap[i][k] + amap[k][j]:
        isnt_add = True
    if not isnt_add:
      cost += amap[i][j]

if isnt_const:
  print(-1)
else:
  print(cost)

Solution (Python):
N=int(input())
import sys
input=sys.stdin.readline
A=[[int(j) for j in input().split()] for _ in range(N)]

ans=0
bridge=[[False]*(N) for i in range(N)]
for k in range(N):
  for i in range(N):
    for j in range(N):
      if i>=j: continue
      if A[i][j]>A[i][k]+A[k][j]:
        print(-1)
        exit(0)

for i in range(N):
  for j in range(N):
    if i >=j :continue
    if all(A[i][j]<A[i][k]+A[k][j] for k in range(N) if k!=i and k!=j):
 
          if not bridge[i][j]:
            ans+=A[i][j] 
            bridge[i][j]=True
print(ans)

Solution (Python):
from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        l = []
        s = d[i][j]
        for k in range(n):
            if k == i or k == j:
                continue
            dist = d[i][k] + d[k][j]
            if dist == s:
                ans -= s
                break
            d[i][j] = min(d[i][j], dist)
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)

Solution (Python):
import copy
def warshall_floyd(d):
    
    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])
 
n = int(input())
a = [[] for i in range(n)]
war = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
war = copy.deepcopy(a)
for i in range(n):
    if a[i][i] != 0:
        print(-1)
        exit()
 
warshall_floyd(war)


res = 0
for i in range(n):
    for j in range(n):
        if war[i][j] < a[i][j]:
            print(-1)
            exit()
        elif war[i][j] == a[i][j]:
            judge = 1
            for h in range(n):
                if h != i and h != j and war[i][h]+war[h][j] == war[i][j]:
                    judge = -1
            if judge == 1:
                res += war[i][j]
print(res//2)

Solution (Python):
def warshall_floyd(n,d):
    
    r = [[float("inf")]*n for i in range(n)]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                r[i][j] = min(d[i][j],r[i][k] + r[k][j])
    return r

n = int(input())
a = [[] for i in range(n)]
for i in range(n):
    a[i] = list(map(int,input().split()))
for i in range(n):
    if a[i][i] != 0:
        print(-1)
        exit()


war = warshall_floyd(n,a)

res = 0
for i in range(n):
    for j in range(n):
        if war[i][j] < a[i][j]:
            print(-1)
            exit()
        elif war[i][j] == a[i][j]:
            judge = 1
            for h in range(n):
                if h != i and h != j and war[i][h]+war[h][j] == war[i][j]:
                    judge = -1
            if judge == 1:
                res += war[i][j]
print(res//2)

Solution (Python):
N=int(input())
inf=float("inf")
Graph=[[inf]*N for i in range(N)]
ans=0
for i in range(N):
  a=[int(m) for m in input().split()]
  for j in range(i+1):
    Graph[i][j]=a[j]
    Graph[j][i]=a[j]
    ans+=a[j]

for i in range(N):
  for j in range(i+1):
    for k in range(N):
      if Graph[i][j]>Graph[i][k]+Graph[k][j]:
        print(-1)
        exit()
      elif Graph[i][j]==Graph[i][k]+Graph[k][j] and i!=k and j!=k:
        ans-=Graph[i][j]
        break

print(ans)

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


dist = [list(A[i]) for i in range(N)]
via = [[None 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 = dist[i][k] + dist[k][j]
            if dist[i][j] >= d:
                dist[i][j] = d
                if i != k and j != k:
                    via[i][j] = k

ans = 0
for i in range(N):
    for j in range(i):
        if dist[i][j] < A[i][j]:
            ans = -1
            break

        if via[i][j] == None:
            ans += dist[i][j]

    if ans == -1:
        break

print(ans)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
import sys
import numpy 
N = int(input())
A = numpy.array([inpl() for _ in range(N)])
ans = 0
for i in range(N):
    A[i][i] = 10**9+1
for i in range(N):
    for j in range(i):
        mindis = numpy.min(A[i] + A[j])
        if mindis > A[i][j]:
            ans += A[i][j]
            continue
        if mindis < A[i][j]:
            print(-1)
            sys.exit()
print(ans)

Solution (Python):
def inpl(): return [int(i) for i in input().split()]
import sys
import numpy 
N = int(input())
A = numpy.asarray([inpl() for _ in range(N)])
ans = 0
for i in range(N):
    A[i][i] = 10**9+1
for i in range(N):
    for j in range(i):
        mindis = numpy.min([A[i] + A[j]])
        if mindis > A[i][j]:
            ans += A[i][j]
            continue
        if mindis < A[i][j]:
            print(-1)
            sys.exit()

print(ans)

Solution (Python):
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i == k or j == k:
                continue
            if A[i][j] == A[i][k] + A[k][j]:
                break
            elif A[i][k] > A[i][j] + A[j][k]:
                print(-1)
                exit()
        else:
            ans += A[i][j]

print(ans)

Solution (Python):
import numpy as np
N=int(input())
dist=[[0.0 for _ in range(N)] for _ in range(N)]

for i in range(N):
    for j,x in enumerate(map(int,input().split())):
        dist[i][j]=float(x)
dist = np.array(dist)
for i in range(N):
    dist[i,i] = float('inf')
ans=0
for i in range(N):
    for j in range(i+1,N):
        min_=min(dist[i]+dist[j])
        if min_<dist[i,j]:
            ans=-1
            break
        elif min_>dist[i,j]:
            ans+=dist[i,j]
    if ans <0:
        break
print(int(ans))

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

N = read()
A = []
for _ in range(N):
  A.append(reads())

necc = [[True] * N for _ in range(N)]

def fail():
  print(-1); exit()

for i, j, k in combinations(range(N), 3):
  if A[i][j] + A[j][k] < A[i][k] or A[i][j] + A[i][k] < A[j][k] or A[i][k] + A[j][k] < A[i][j]:
    fail()
  if A[i][j] + A[j][k] == A[i][k]:
    necc[i][k] = False
  if A[i][j] + A[i][k] == A[j][k]:
    necc[j][k] = False
  if A[i][k] + A[j][k] == A[i][j]:
    necc[i][j] = False

ans = sum(A[i][j] for i, j in combinations(range(N), 2) if necc[i][j])
print(ans)

Solution (Python):
import sys
import copy

N = int(input())
table = []
for i in range(N):
    A = [int(j) for j in input().split()]
    table.append(A)
tas = copy.deepcopy(table)
for k in range(N):
    for i in range(N):
        for j in range(N):
            tas[j][i] = min(tas[j][i], tas[j][k] + tas[k][i])

for y in range(N):
    for x in range(y+1, N):
        if table[y][x] != tas[y][x]:
            print(-1)
            sys.exit()
ans = 0
for i in range(N):
    for j in range(i + 1, N):
        flag = True
        for k in range(N):
            if i == k or j == k:
                continue
            if table[j][i] >= table[j][k] + table[k][i]:
                flag = False
        if flag:
            ans += table[j][i]
print(ans)

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq,copy





def warshall_floyd(d):
    """Warshall Floyd method"""

    n = len(d)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

def solve(f):
    n = f.read_int()
    a = [f.read_int_list() for _ in xrange(n)]

    aorg = copy.deepcopy(a)
    warshall_floyd(a)

    for i in xrange(n):
        for j in xrange(n):
            if aorg[i][j] != a[i][j]: return -1

    ans = 0
    for i in xrange(n):
        for j in xrange(n):
            if i == j: continue
            for k in xrange(n):
                if i == k or j == k: continue
                if a[i][j] == a[i][k] + a[k][j]: break
            else:
                ans += a[i][j]

    return ans/2


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

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

ans = 0
muri = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		equals = []
		max_length = 0
		for k in range(n):
			if k == i or k == j:
				continue
			elif a[i][k] + a[k][j] == a[i][j]:
				max_length = float("inf")
				equals.append(a[i][k] + a[k][j])
			elif a[i][k] + a[k][j] < a[i][j]:
				muri += 1
			if a[i][k] + a[k][j] > max_length:
				max_length = a[i][k] + a[k][j]
		if max_length < a[i][j]:
			muri += 1
		if max_length < 10 ** 10:
			ans += a[i][j]
		elif len(equals) >= 2:
			if a[i][j] != min(equals):
				muri += 1

if n == 2:
	print(a[0][1])
elif muri != 0:
	print(-1)
else:
	print(ans)

Solution (Python):

def inpl(): return tuple(map(int, input().split()))
from itertools import product, combinations

def main():
    N = int(input())
    adj = [inpl() for _ in range(N)]
    need = [[True]*N for _ in range(N)]
    ok = True
    res = 0
    for k, i, j in product(range(N), repeat=3):
        if adj[i][j] < adj[i][k] + adj[k][j]:
            continue
        elif i == k or j == k:
            continue
        elif adj[i][j] == adj[i][k] + adj[k][j]:
            need[i][j] = False
            need[j][i] = False
        else:
            ok = False
    if ok:
        for i, j in combinations(range(N), 2):
            if need[i][j]:
                res += adj[i][j]
        print(res)
    else:
        print(-1)

main()

Solution (Python):

def inpl(): return tuple(map(int, input().split()))
from itertools import product

def main():
    N = int(input())
    adj = [inpl() for _ in range(N)]
    need = [[True]*N for _ in range(N)]
    ok = True
    res = 0
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if adj[i][j] < adj[i][k] + adj[k][j]:
                    continue
                elif i == k or j == k:
                    continue
                elif adj[i][j] == adj[i][k] + adj[k][j]:
                    need[i][j] = False
                    need[j][i] = False
                else:
                    ok = False
    if ok:
        for i in range(N):
            for j in range(i+1, N):
                if need[i][j]:
                    res += adj[i][j]
        print(res)
    else:
        print(-1)

main()

Solution (Python):

from itertools import combinations
 
def inpl(): return list(map(int, input().split()))
 
N = int(input())
res = 0
exist = True
A = []
 
for _ in range(N):
    A.append(inpl())
 
for i, j in combinations(range(N), 2):
    vervose = False
 
    if not exist:
        break
 
    for k in range(N):
        if i == k or j == k:
            pass
        else:
            if A[i][j] < A[i][k] + A[k][j]:
                pass
            elif A[i][j] == A[i][k] + A[k][j]:
                vervose = True
            else:
                exist = False
                break
    if vervose:
        pass
    else:
        res += A[i][j]
 
if exist:
    print(res)
else:
    print(-1)

Solution (Python):

from itertools import combinations

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

N = int(input())
res = 0
exist = True
A = []

for _ in range(N):
    A.append(inpl())

for i, j in combinations(range(N), 2):
    vervose = False

    for k in range(N):
        if A[i][j] > A[i][k] + A[k][j]:
            exist = False
            break
    
    if not exist:
        break
    
    for k in range(N):
        if i == k or j == k:
            pass
        elif A[i][j] == A[i][k] + A[k][j]:
            vervose = True
            break
        
    if not vervose:
        res += A[i][j]
if exist:
    print(res)
else:
    print(-1)