Buggy python submission (verdict: Time Limit Exceeded):
N = int(raw_input())
A = [map(int, raw_input().split(' ')) for n in [0]*N]
for i in xrange(N): A[i][i] = 1000000000

answer = 0
for i, Ai in enumerate(A):
  for j, Aj in enumerate(A[:i]):
    Aij = Ai[j]
    no_other_route = 1
    for k in xrange(N):
      L = Ai[k] + Aj[k]
      if Aij >= L:
        if Aij > L:
          print -1
          exit()
        no_other_route = 0
    answer += Aij * no_other_route

print answer

Fixed submission:
N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))
  A[n][n] = 1000000001

answer = 0
for i in range(N):
  Ai = A[i]
  for j in range(i):
    Aij = Ai[j]
    L = min(map(sum, zip(Ai, A[j])))
    if Aij < L:
      answer += Aij
    else:
      if Aij > L:
        print -1
        exit()
print answer

Buggy python submission (verdict: Time Limit Exceeded):
N = int(raw_input())
A = [map(int, raw_input().split(' ')) for n in xrange(N)]

answer = 0
for i in xrange(N):
  Ai = A[i]
  for j in xrange(i):
    Aj = A[j]
    Aij = Ai[j]
    no_other_route = 1
    for k in xrange(N):
      L = Ai[k] + Aj[k]
      if Aij >= L:
        if Aij > L:
          print -1
          exit()
        if k == i or k == j: continue
        no_other_route = 0
    answer += Aij * no_other_route

print answer

Fixed submission:
N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))
  A[n][n] = 1000000001

answer = 0
for i in range(N):
  Ai = A[i]
  for j in range(i):
    Aij = Ai[j]
    L = min(map(sum, zip(Ai, A[j])))
    if Aij < L:
      answer += Aij
    else:
      if Aij > L:
        print -1
        exit()
print answer

Buggy python submission (verdict: Time Limit Exceeded):
N = int(raw_input())
A = []
B = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))
  B.append(A[-1]+[])

for i in xrange(N):
  for j in xrange(i):
    for k in xrange(j):
      L1 = A[i][k] + A[k][j]
      L2 = A[k][j] + A[j][i]
      L3 = A[j][i] + A[i][k]
      if A[i][j] > L1 or A[k][i] > L2 or A[j][k] > L3:
        print -1
        exit()
      if A[i][j] == L1: B[i][j] = B[j][i] = 0
      if A[k][i] == L2: B[k][i] = B[i][k] = 0
      if A[j][k] == L3: B[j][k] = B[k][j] = 0

print sum(map(sum, B))/2

Fixed submission:
N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))
  A[n][n] = 1000000001

answer = 0
for i in range(N):
  Ai = A[i]
  for j in range(i):
    Aij = Ai[j]
    L = min(map(sum, zip(Ai, A[j])))
    if Aij < L:
      answer += Aij
    else:
      if Aij > L:
        print -1
        exit()
print answer

Buggy python submission (verdict: Time Limit Exceeded):
N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))

answer = 0
for i in xrange(N):
  for j in xrange(i):
    other_route = False
    for k in xrange(N):
      if k == i or k == j:
        continue
      L = A[i][k] + A[k][j]
      if A[i][j] == L:
        other_route = True
      elif A[i][j] > L:
        print -1
        exit()
    if not other_route:
      answer += A[i][j]

print answer

Fixed submission:
N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))
  A[n][n] = 1000000001

answer = 0
for i in range(N):
  Ai = A[i]
  for j in range(i):
    Aij = Ai[j]
    L = min(map(sum, zip(Ai, A[j])))
    if Aij < L:
      answer += Aij
    else:
      if Aij > L:
        print -1
        exit()
print answer

Buggy python submission (verdict: Time Limit Exceeded):
N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))

memo = {}
def route(f, t, now, arrived):
  if now == t:
    return 0
  if (t, now, tuple(arrived)) in memo:
    return memo[(t, now, tuple(arrived))]
  min_dist = float('inf')
  for k in xrange(N):
    if k in arrived or (k == t and len(arrived) == 1):
      continue
    min_dist = min(route(f, t, k, arrived|set([k]))+A[now][k], min_dist)
  memo[(t, now, tuple(arrived))] = min_dist
  return min_dist

answer = 0
for i in xrange(N):
  for j in xrange(i):
    L = route(i, j, i, set([i]))
    if A[i][j] == L:
      pass
    elif A[i][j] > L:
      print -1
      exit()
    else:
      answer += A[i][j]

print answer

Fixed submission:
N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))
  A[n][n] = 1000000001

answer = 0
for i in range(N):
  Ai = A[i]
  for j in range(i):
    Aij = Ai[j]
    L = min(map(sum, zip(Ai, A[j])))
    if Aij < L:
      answer += Aij
    else:
      if Aij > L:
        print -1
        exit()
print answer

Buggy python submission (verdict: Time Limit Exceeded):
N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))

def route(f, t, now, arrived):
  if now == t:
    return 0
  min_dist = float('inf')
  for k in xrange(N):
    if k in arrived or (k == t and len(arrived) == 1):
      continue
    min_dist = min(route(f, t, k, arrived|set([k]))+A[now][k], min_dist)
  return min_dist

answer = 0
for i in xrange(N):
  for j in xrange(i):
    L = route(i, j, i, set([i]))
    if A[i][j] == L:
      pass
    elif A[i][j] > L:
      print -1
      exit()
    else:
      answer += A[i][j]

print answer

Fixed submission:
N = int(raw_input())
A = []
for n in xrange(N):
  A.append(map(int, raw_input().split(' ')))
  A[n][n] = 1000000001

answer = 0
for i in range(N):
  Ai = A[i]
  for j in range(i):
    Aij = Ai[j]
    L = min(map(sum, zip(Ai, A[j])))
    if Aij < L:
      answer += Aij
    else:
      if Aij > L:
        print -1
        exit()
print answer