Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    for k in range(N):
      if i == k: continue
      if j == 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]:
        break
    else:
      ans += A[i][j]

print(ans)

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

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    for k in range(N):
      if i == k: continue
      if j == 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]:
        break
    else:
      ans += A[i][j]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

D = [[0] * N for i in range(N)]

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

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

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    if A[i][j] > D[i][j]:
      print(-1)
      exit()
    for k in range(N):
      if i == k: continue
      if j == k: continue
      if D[i][j] == D[i][k] + D[k][j]:
        break
    else:
      ans += D[i][j]

print(ans)

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

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    for k in range(N):
      if i == k: continue
      if j == 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]:
        break
    else:
      ans += A[i][j]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

L.sort()

class Tree:
  def __init__(s, N):
    s.T = [-1] * N
  def root(s, x):
    if s.T[x] < 0:
      return x, -s.T[x]
    r, d = s.root(s.T[x])
    s.T[x] = r
    return r, d
  def merge(s, a, b):
    ar, ad = s.root(a)
    br, bd = s.root(b)
    if ar == br:
      return True
    if ad < bd:
      s.T[ar] = -max(ad, bd + 1)
      s.T[br] = ar
    else:
      s.T[br] = -max(bd, ad + 1)
      s.T[ar] = br
    return False

class Data():
  class Node():
    def __init__(s):
      s.R = {}
      s.reset()
    def reset(s):
      s.done = False
      s.cos = -1
    def set(s, a, x):
      s.R[a] = x

  def __init__(s, N):
    s.nodes = [s.Node() for _ in range(N)]
  def set(s, a, b, x):
    s.nodes[a].set(b, x)
    s.nodes[b].set(a, x)
  def dist(s, a, b, f):
    if f:
      s.dijk(a)
    return s.nodes[b].cos
  def dijk(s, a):
    for n in s.nodes:
      n.reset()
    s.nodes[a].cos = 0
    while True:
      dn = None
      for n in s.nodes:
        if n.done or n.cos < 0: continue
        if dn == None or n.cos < dn.cos:
          dn = n
      if dn == None:
        break
      dn.done = True
      for k, v in dn.R.items():
        n = s.nodes[k]
        if n.done: continue
        if n.cos == -1 or n.cos > dn.cos + v:
          n.cos = dn.cos + v
t = Tree(N)
d = Data(N)
ans = 0
for i in range(len(L)):
  x, a, b = L[i]
  if t.merge(a, b):
    if d.dist(a, b, True) != x:
      d.set(a, b, x)
      ans += x
  else:
    d.set(a, b, x)
    ans += x

for i in range(N - 1):
  if d.dist(i, i + 1, True) != A[i][i + 1]:
    break
  for j in range(i + 2, N):
    if d.dist(i, j, False) != A[i][j]:
      break
  else:
    continue
  break
else:
  print(ans)
  exit()

print(-1)



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

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    for k in range(N):
      if i == k: continue
      if j == 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]:
        break
    else:
      ans += A[i][j]

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

L.sort()

class Tree:
  def __init__(s, N):
    s.T = [-1] * N
  def root(s, x):
    if s.T[x] < 0:
      return x, -s.T[x]
    r, d = s.root(s.T[x])
    s.T[x] = r
    return r, d
  def merge(s, a, b):
    ar, ad = s.root(a)
    br, bd = s.root(b)
    if ar == br:
      return True
    if ad < bd:
      s.T[ar] = -max(ad, bd + 1)
      s.T[br] = ar
    else:
      s.T[br] = -max(bd, ad + 1)
      s.T[ar] = br
    return False

class Data():
  class Node():
    def __init__(s):
      s.R = {}
      s.reset()
    def reset(s):
      s.done = False
      s.cos = -1
    def set(s, a, x):
      s.R[a] = x

  def __init__(s, N):
    s.nodes = [s.Node() for _ in range(N)]
  def set(s, a, b, x):
    s.nodes[a].set(b, x)
    s.nodes[b].set(a, x)
  def dist(s, a, b, f):
    if f:
      s.dijk(a)
    return s.nodes[b].cos
  def dijk(s, a):
    for n in s.nodes:
      n.reset()
    s.nodes[a].cos = 0
    while True:
      dn = None
      for n in s.nodes:
        if n.done or n.cos < 0: continue
        if dn == None or n.cos < dn.cos:
          dn = n
      if dn == None:
        break
      dn.done = True
      for k, v in dn.R.items():
        n = s.nodes[k]
        if n.done: continue
        if n.cos == -1 or n.cos > dn.cos + v:
          n.cos = dn.cos + v
t = Tree(N)
d = Data(N)
ans = 0
for i in range(len(L)):
  x, a, b = L[i]
  if t.merge(a, b):
    if d.dist(a, b, True) != x:
      d.set(a, b, x)
      ans += x
  else:
    d.set(a, b, x)
    ans += x

for i in range(N - 1):
  if d.dist(i, i + 1, True) != A[i][i + 1]:
    break
  for j in range(i + 2, N):
    if d.dist(i, j, False) != A[i][j]:
      break
  else:
    continue
  break
else:
  print(ans)
  exit()

print(-1)



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

L = []
for i in range(N):
  for j in range(i + 1, N):
    L.append([A[i][j], i, j])

ans = 0
for i in range(N - 1):
  for j in range(i + 1, N):
    for k in range(N):
      if i == k: continue
      if j == 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]:
        break
    else:
      ans += A[i][j]

print(ans)