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

    dist = [[a[i][j] for j in range(n)] for i in range(n)]
    total = sum([sum(a[i]) for i in range(n)])
    for k in range(n):
        for i in range(n):
            if k==i:
                continue
            for j in range(n):
                if i == j or k ==j:
                    continue
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    print(-1)
                    exit()
                if dist[i][j] == dist[i][k] + dist[k][j]:
                    total -= dist[i][j]
    print(total//2)
    

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    n = int(input())
    a = [list(map(int, input().split())) for i in range(n)]

    total = sum([sum(a[i]) for i in range(n)])
    for k in range(n):
        for i in range(n):
            if k == i:
                continue
            for j in range(n):
                if i == j or k == j:
                    continue
                if a[i][j] > a[i][k] + a[k][j]:
                    print(-1)
                    exit()
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if i == k or j == k:
                    continue
                if a[i][j] == a[i][k] + a[k][j]:
                    total -= a[i][j]
                    break

    print(total//2)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import heapq


def dijkstra(graph, root, goal, limit):
    # print('dijkstra',root, goal, limit)
    # print(graph)
    dist = [float('inf')] * len(graph)
    dist[root] = 0
    q = [(0, root)]
    while q:
        d, v = heapq.heappop(q)
        # print(d,v)
        if dist[v] < d:
            continue
        if d == goal:
            return dist

        limit_over = True
        for cost, target in graph[v]:
            # print(d,v, cost, target, dist)
            if dist[target] > dist[v] + cost:
                dist[target] = dist[v] + cost
                heapq.heappush(q, (dist[target], target))
                # print('heapq',q)
            if dist[v] + cost <= limit:
                limit_over = False
        if limit_over:
            # print('limit')
            return dist
    return dist

def main():
    n = int(input())
    a = [list(map(int, input().split())) for i in range(n)]

    h = []
    for i in range(n):
        for j in range(i+1, n):
            heapq.heappush(h, (a[i][j], i, j))

    graph = [[] for i in range(n)]
    total = 0
    while h:
        cost, s, t = heapq.heappop(h)
        dist = dijkstra(graph, s, t, cost)
        if dist[t] < cost:
            print(-1)
            exit()
        elif dist[t] > cost:
            total += cost
            # print(total, s, t, cost, dist[t])
            graph[s].append((cost, t))
            graph[t].append((cost, s))
            dist = dijkstra(graph, s, t, cost)

    # print(*graph, sep = '\n')
    print(total)
        
    
if __name__ == '__main__':
    main()

Fixed submission:
def main():
    n = int(input())
    a = [list(map(int, input().split())) for i in range(n)]

    total = sum([sum(a[i]) for i in range(n)])
    for k in range(n):
        for i in range(n):
            if k == i:
                continue
            for j in range(n):
                if i == j or k == j:
                    continue
                if a[i][j] > a[i][k] + a[k][j]:
                    print(-1)
                    exit()
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if i == k or j == k:
                    continue
                if a[i][j] == a[i][k] + a[k][j]:
                    total -= a[i][j]
                    break

    print(total//2)


if __name__ == '__main__':
    main()