Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappop, heappush


def bfs(x, y):
    path = [float('inf')] * N
    q = []
    heappush(q, (0, x))
    path[x] = 0

    while q:
        s, p = heappop(q)
        for np, d in edge[p]:
            nd = path[p] + d
            if path[np] > nd:
                path[np] = nd
                heappush(q, (nd, np))
    
    return path[y]


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
q = []
for i in range(N):
    for j in range(i + 1, N):
        q.append((A[i][j], i, j))

q.sort()

# B = [[float('inf')] * N for _ in range(N)]

ans = 0
edge = [[] for _ in range(N)]
for a, i, j in q:
    b = bfs(i, j)
    if a < b:
        edge[i].append((j, a))
        edge[j].append((i, a))
        ans += a
    elif a == b:
        pass
    else:
        print(-1)
        exit()

print(ans)


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

dp = A
cnt = 0
for i in range(N):
    for j in range(N):
        if all(dp[i][j] < dp[i][k] + dp[k][j] for k in range(N) if k != i and k != j):
            cnt += dp[i][j]
        if any(dp[i][j] > dp[i][k] + dp[k][j] for k in range(N)):
            print(-1)
            exit()

print(cnt // 2)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


def bfs(x, y):
    path = [float('inf')] * N
    q = deque()
    q.append(x)
    path[x] = 0
    while q:
        p = q.popleft()
        for np, d in edge[p]:
            if path[np] > path[p] + d:
                path[np] = path[p] + d
                q.append(np)
    
    return path[y]


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
q = []
for i in range(N):
    for j in range(i + 1, N):
        q.append((A[i][j], i, j))

q.sort()

# B = [[float('inf')] * N for _ in range(N)]

ans = 0
edge = [[] for _ in range(N)]
for a, i, j in q:
    b = bfs(i, j)
    if a < b:
        edge[i].append((j, a))
        edge[j].append((i, a))
        ans += a
    elif a == b:
        pass
    else:
        print(-1)
        exit()

print(ans)


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

dp = A
cnt = 0
for i in range(N):
    for j in range(N):
        if all(dp[i][j] < dp[i][k] + dp[k][j] for k in range(N) if k != i and k != j):
            cnt += dp[i][j]
        if any(dp[i][j] > dp[i][k] + dp[k][j] for k in range(N)):
            print(-1)
            exit()

print(cnt // 2)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
from collections import deque


def bfs(x, y):
    path = [float('inf')] * N
    q = deque()
    q.append(x)
    path[x] = 0
    while q:
        p = q.popleft()
        for np, d in edge[p]:
            if path[np] > path[p] + d:
                path[np] = path[p] + d
                q.append(np)
    
    return path[y]


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
q = []
for i in range(N):
    for j in range(i + 1, N):
        heappush(q, (A[i][j], i, j))

ans = 0
edge = [[] for _ in range(N)]
while q:
    a, i, j = heappop(q)
    b = bfs(i, j)
    if a < b:
        edge[i].append((j, a))
        edge[j].append((i, a))
        ans += a
    elif a == b:
        pass
    else:
        print(-1)
        exit()

print(ans)


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

dp = A
cnt = 0
for i in range(N):
    for j in range(N):
        if all(dp[i][j] < dp[i][k] + dp[k][j] for k in range(N) if k != i and k != j):
            cnt += dp[i][j]
        if any(dp[i][j] > dp[i][k] + dp[k][j] for k in range(N)):
            print(-1)
            exit()

print(cnt // 2)