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

    update = False
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if not (dist[i][k] and dist[k][j]): continue  # パスなし
                d = dist[i][k] + dist[k][j]
                if dist[i][j] > d:
                    dist[i][j] = d
                    update = True

    if update:
        print(-1)
        return

    ans = 0
    for j in range(N):
        for i in range(j):
            for k in range(N):
                if not (dist[i][k] and dist[k][j]): continue  # パスなし
                d = dist[i][k] + dist[k][j]
                if d == dist[i][j]: break  # divisible
            else:
                ans += dist[i][j]
    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


Fixed submission:
INF = 10 ** 12

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

for i in range(N):
    for j in range(N):
        for k in range(N):
            if a[i][j] > a[i][k] + a[k][j]:
                print(-1)
                exit()

res = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i != k and j != k and a[i][j] == a[i][k] + a[k][j]:
                break
        else:
            res += a[i][j]

print(res)

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

    n = int(input())
    a = [[int(x) for x in input().split()] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if a[i][j] != min(a[i][k] + a[k][j] for k in range(n)):
                print(-1)
                return

    h = []
    for r, row in enumerate(a):
        for c, cell in enumerate(row):
            if r == c: break
            bit = (1 << r) | (1 << c)
            heappush(h, (cell, bit))  # dist,bit

    pathes = set()
    while h:
        dist, bit = heappop(h)

        is_path = True
        for d1, p1 in pathes:
            for d2, p2 in pathes:
                xor = p1 ^ p2
                if (xor == bit) and (dist >= d1 + d2):
                    is_path = False
                    break
            if not is_path:
                break

        if is_path:
            pathes.add((dist, bit))

    print(sum(map(itemgetter(0), pathes)))


if __name__ == '__main__':
    main()


Fixed submission:
INF = 10 ** 12

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

for i in range(N):
    for j in range(N):
        for k in range(N):
            if a[i][j] > a[i][k] + a[k][j]:
                print(-1)
                exit()

res = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i != k and j != k and a[i][j] == a[i][k] + a[k][j]:
                break
        else:
            res += a[i][j]

print(res)

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

    n = int(input())
    a = [[int(x) for x in input().split()] for _ in range(n)]

    for i in range(n):
        for j in range(n):
            if a[i][j] != min(a[i][k] + a[k][j] for k in range(n)):
                print(-1)
                return

    h = []
    for r, row in enumerate(a):
        for c, cell in enumerate(row):
            if r == c: break
            bit = (1 << r) | (1 << c)
            heappush(h, (cell, bit))  # dist,bit

    pathes = set()
    while h:
        dist, bit = heappop(h)

        is_path = True
        for d1, p1 in pathes:
            for d2, p2 in pathes:
                xor = p1 ^ p2
                if (xor == bit) and (dist >= d1 + d2):
                    is_path = False
                    break
            if not is_path:
                break

        if is_path:
            pathes.add((dist, bit))

    print(sum(map(itemgetter(0), pathes)))


if __name__ == '__main__':
    main()


Fixed submission:
INF = 10 ** 12

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

for i in range(N):
    for j in range(N):
        for k in range(N):
            if a[i][j] > a[i][k] + a[k][j]:
                print(-1)
                exit()

res = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i != k and j != k and a[i][j] == a[i][k] + a[k][j]:
                break
        else:
            res += a[i][j]

print(res)

Buggy python submission (verdict: Time Limit Exceeded):
INF = 10 ** 12

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

for i in range(N):
    for j in range(N):
        for k in range(N):
            if a[i][j] > a[i][k] + a[k][j]:
                print(-1)
                exit()

res = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i != k and j != k and a[i][j] == a[i][k] + a[k][j]:
                break
        else:
            res += a[i][j]

print(res)


Fixed submission:
INF = 10 ** 12

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

for i in range(N):
    for j in range(N):
        for k in range(N):
            if a[i][j] > a[i][k] + a[k][j]:
                print(-1)
                exit()

res = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i != k and j != k and a[i][j] == a[i][k] + a[k][j]:
                break
        else:
            res += a[i][j]

print(res)