Buggy python submission (verdict: Time Limit Exceeded):
INF = 10 ** 20
n = int(input())
edges = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * n for _ in range(n)]

edgeList = []
for i in range(n):
    for j in range(i, n):
        edgeList.append((edges[i][j], i, j))
edgeList.sort()

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], edges[i][k] + edges[k][j])
ans = 0
for c, i, j in edgeList:
    minCost = min([dist[i][k] + dist[k][j] for k in range(n) if (k != i and k != j)] + [INF])
    if c > minCost:
        print(-1)
        break
    if c < minCost:
        ans += c
else:
    print(ans)

Fixed submission:
INF = 10 ** 20
n = int(input())
edges = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * n for _ in range(n)]

edgeList = []
for i in range(n):
    for j in range(i, n):
        edgeList.append((edges[i][j], i, j))
edgeList.sort()

for k in range(n):
    edgesk = edges[k]
    for i in range(n):
        disti = dist[i]
        edgesik = edges[i][k]
        for j in range(n):
            if disti[j] > edgesik + edgesk[j]:
                disti[j] = edgesik + edgesk[j]

ans = 0
for c, i, j in edgeList:
    minCost = INF
    for k in range(n):
        if k in (i, j):continue
        if minCost > dist[i][k] + dist[k][j]:
            minCost = dist[i][k] + dist[k][j]
    if c > minCost:
        print(-1)
        break
    if c < minCost:
        ans += c
else:
    print(ans)

Buggy python submission (verdict: Runtime Error):
INF = 10 ** 20
n = int(input())
edges = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * n for _ in range(n)]

edgeList = []
for i in range(n):
    for j in range(i, n):
        edgeList.append((edges[i][j], i, j))
edgeList.sort()

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], edges[i][k] + edges[k][j])
ans = 0
for c, i, j in edgeList:
    minCost = min([dist[i][k] + dist[k][j] for k in range(n) if (k != i and k != j)])
    if c > minCost:
        print(-1)
        break
    if c < minCost:
        ans += c

else:
    print(ans)

Fixed submission:
INF = 10 ** 20
n = int(input())
edges = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * n for _ in range(n)]

edgeList = []
for i in range(n):
    for j in range(i, n):
        edgeList.append((edges[i][j], i, j))
edgeList.sort()

for k in range(n):
    edgesk = edges[k]
    for i in range(n):
        disti = dist[i]
        edgesik = edges[i][k]
        for j in range(n):
            if disti[j] > edgesik + edgesk[j]:
                disti[j] = edgesik + edgesk[j]

ans = 0
for c, i, j in edgeList:
    minCost = INF
    for k in range(n):
        if k in (i, j):continue
        if minCost > dist[i][k] + dist[k][j]:
            minCost = dist[i][k] + dist[k][j]
    if c > minCost:
        print(-1)
        break
    if c < minCost:
        ans += c
else:
    print(ans)

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

INF = 10 ** 20
n = int(input())
que = []
for i in range(n):
    aList = list(map(int, input().split()))
    for j in range(i, n):
        heappush(que, (aList[j], i, j))

dist = [[INF] * n for _ in range(n)]
ans = 0
while que:
    c, i, j = heappop(que)
    minDist = INF
    for k in range(n):
        minDist = min(minDist, dist[i][k] + dist[k][j])
    if minDist < c:
        print(-1)
        break
    elif minDist == c:
        continue
    else:
        dist[i][j] = dist[j][i] = c
        ans += c
else:
    print(ans)



Fixed submission:
INF = 10 ** 20
n = int(input())
edges = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * n for _ in range(n)]

edgeList = []
for i in range(n):
    for j in range(i, n):
        edgeList.append((edges[i][j], i, j))
edgeList.sort()

for k in range(n):
    edgesk = edges[k]
    for i in range(n):
        disti = dist[i]
        edgesik = edges[i][k]
        for j in range(n):
            if disti[j] > edgesik + edgesk[j]:
                disti[j] = edgesik + edgesk[j]

ans = 0
for c, i, j in edgeList:
    minCost = INF
    for k in range(n):
        if k in (i, j):continue
        if minCost > dist[i][k] + dist[k][j]:
            minCost = dist[i][k] + dist[k][j]
    if c > minCost:
        print(-1)
        break
    if c < minCost:
        ans += c
else:
    print(ans)