Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

N = int(readline())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))
  
# まずワーシャルフロイド表を作る
# ワーシャルフロイド表より大きな数値が元の表にあったら、最短距離の表ではないので-1
# 最短距離の表になっているのであれば、
# A[1][3]に行くときにA[1][2] + A[2][3]となるのであれば、
# A[1][3]のほうだけansに記録していく

import copy
newA = copy.deepcopy(A)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if i == k or k == j or i == j:
        continue
      if A[i][k] + A[k][j] < A[i][j]:
        print(-1)
        exit(0)
      elif A[i][k] + A[k][j] == A[i][j]:
        # A[i][j]の道路は不要
        newA[i][j] = 0

ans = 0
for a in newA:
  ans += sum(a)
print(ans // 2)

Fixed submission:
import sys
readline = sys.stdin.readline

N = int(readline())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))
  
# まずワーシャルフロイド表を作る
# ワーシャルフロイド表より大きな数値が元の表にあったら、最短距離の表ではないので-1
# 最短距離の表になっているのであれば、
# A[1][3]に行くときにA[1][2] + A[2][3]となるのであれば、
# A[1][3]のほうだけansに記録していく

import copy
newA = copy.deepcopy(A)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if i == k or k == j or i == j:
        continue
      if A[i][k] + A[k][j] < A[i][j]:
        print(-1)
        exit(0)
      elif A[i][k] + A[k][j] == A[i][j]:
        # A[i][j]の道路は不要
        newA[i][j] = 0

ans = 0
for a in newA:
  ans += sum(a)
print(ans // 2)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

N = int(readline())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))
  
# まずワーシャルフロイド表を作る
# ワーシャルフロイド表より大きな数値が元の表にあったら、最短距離の表ではないので-1
# 最短距離の表になっているのであれば、
# A[1][3]に行くときにA[1][2] + A[2][3]となるのであれば、
# A[1][3]のほうだけansに記録していく

ans = 0
for a in A:
  ans += sum(a)
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      if i == k or k == j or i == j:
        continue
      if A[i][k] + A[k][j] < A[i][j]:
        print(-1)
        exit(0)
      if A[i][k] + A[k][j] == A[i][j]:
        ans -= A[i][j]
        
print(ans // 2)

Fixed submission:
import sys
readline = sys.stdin.readline

N = int(readline())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))
  
# まずワーシャルフロイド表を作る
# ワーシャルフロイド表より大きな数値が元の表にあったら、最短距離の表ではないので-1
# 最短距離の表になっているのであれば、
# A[1][3]に行くときにA[1][2] + A[2][3]となるのであれば、
# A[1][3]のほうだけansに記録していく

import copy
newA = copy.deepcopy(A)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if i == k or k == j or i == j:
        continue
      if A[i][k] + A[k][j] < A[i][j]:
        print(-1)
        exit(0)
      elif A[i][k] + A[k][j] == A[i][j]:
        # A[i][j]の道路は不要
        newA[i][j] = 0

ans = 0
for a in newA:
  ans += sum(a)
print(ans // 2)

Buggy python submission (verdict: Runtime Error):
import sys
readline = sys.stdin.readline

N = int(readline())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))
  
# まずワーシャルフロイド表を作る
# ワーシャルフロイド表より大きな数値が元の表にあったら、最短距離の表ではないので-1
# 最短距離の表になっているのであれば、
# A[1][3]に行くときにA[1][2] + A[2][3]となるのであれば、
# A[1][3]のほうだけansに記録していく

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense
A = np.array(A)
G = csgraph_from_dense(A, null_value=0)
w = floyd_warshall(G)

for i in range(N):
  for j in range(N):
    if A[i][j] > w[i][j]:
      print(-1)
      exit(0)

ans = 0
for a in A:
  ans += sum(a)
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      if i == k or k == j or i == j:
        continue
      if A[i][k] + A[k][j] == A[i][j]:
        ans -= A[i][j]
        
print(ans // 2)

Fixed submission:
import sys
readline = sys.stdin.readline

N = int(readline())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))
  
# まずワーシャルフロイド表を作る
# ワーシャルフロイド表より大きな数値が元の表にあったら、最短距離の表ではないので-1
# 最短距離の表になっているのであれば、
# A[1][3]に行くときにA[1][2] + A[2][3]となるのであれば、
# A[1][3]のほうだけansに記録していく

import copy
newA = copy.deepcopy(A)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if i == k or k == j or i == j:
        continue
      if A[i][k] + A[k][j] < A[i][j]:
        print(-1)
        exit(0)
      elif A[i][k] + A[k][j] == A[i][j]:
        # A[i][j]の道路は不要
        newA[i][j] = 0

ans = 0
for a in newA:
  ans += sum(a)
print(ans // 2)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
readline = sys.stdin.readline

N = int(readline())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))
  
# まずワーシャルフロイド表を作る
# ワーシャルフロイド表より大きな数値が元の表にあったら、最短距離の表ではないので-1
# 最短距離の表になっているのであれば、
# A[1][3]に行くときにA[1][2] + A[2][3]となるのであれば、
# A[1][3]のほうだけansに記録していく

import numpy as np
from scipy.sparse.csgraph import shortest_path
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse.csgraph import csgraph_from_dense
A = np.array(A)
G = csgraph_from_dense(A, null_value=0)
w = floyd_warshall(G)

for i in range(N):
  for j in range(N):
    if A[i][j] > w[i][j]:
      print(-1)
      exit(0)

ans = 0
for a in A:
  ans += sum(a)
  
for k in range(N):
  for i in range(N):
    for j in range(N):
      if i == k or k == j or i == j:
        continue
      if A[i][k] + A[k][j] == A[i][j]:
        ans -= A[i][j]
        
print(ans // 2)

Fixed submission:
import sys
readline = sys.stdin.readline

N = int(readline())

A = [None] * N
for i in range(N):
  A[i] = list(map(int,readline().split()))
  
# まずワーシャルフロイド表を作る
# ワーシャルフロイド表より大きな数値が元の表にあったら、最短距離の表ではないので-1
# 最短距離の表になっているのであれば、
# A[1][3]に行くときにA[1][2] + A[2][3]となるのであれば、
# A[1][3]のほうだけansに記録していく

import copy
newA = copy.deepcopy(A)

for k in range(N):
  for i in range(N):
    for j in range(N):
      if i == k or k == j or i == j:
        continue
      if A[i][k] + A[k][j] < A[i][j]:
        print(-1)
        exit(0)
      elif A[i][k] + A[k][j] == A[i][j]:
        # A[i][j]の道路は不要
        newA[i][j] = 0

ans = 0
for a in newA:
  ans += sum(a)
print(ans // 2)