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

INF = float('inf')
graph = [[INF for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        graph[i][j] = a[i][j]

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(n):
    for j in range(n):
        if graph[i][j] < a[i][j]:
            print(-1)
            exit()

ans = 0

for i in range(n):
    for j in range(i+1, n):
        v = INF
        for k in range(n):
            if k == i or k == j:
                continue
            v = min(v, graph[i][k] + graph[k][j])
        if v != graph[i][j]:
            ans += graph[i][j]

print(ans)

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

INF = float('inf')
graph = [[INF for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        graph[i][j] = a[i][j]

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(n):
    for j in range(n):
        if graph[i][j] < a[i][j]:
            print(-1)
            exit()

ans = 0

for i in range(n):
    for j in range(i+1, n):
        v = INF
        for k in range(n):
            if k == i or k == j:
                continue
            v = min(v, graph[i][k] + graph[k][j])
        if v != graph[i][j]:
            ans += graph[i][j]

print(ans)

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

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

INF = float('inf')

def dijkstra(s, g, key):
    dist = [INF for i in range(n)]
    dist[s] = 0
    hq2 = [(0, s)]
    while hq2:
        cost, node = heapq.heappop(hq2)
        if cost > dist[node]:
            continue
        for v_next, d_next in enumerate(graph[node]):
            if d_next == INF:
                continue
            d = d_next + cost
            if d < dist[v_next]:
                dist[v_next] = d
                heapq.heappush(hq2, (dist[v_next], v_next))
    if dist[g] > key:
        graph[s][g] = key
        graph[g][s] = key
        return key
    elif dist[g] == key:
        return 0
    else:
        return -1

ans = 0
hq = []
for i in range(n-1):
    for j in range(i+1, n):
        heapq.heappush(hq, (a[i][j], i, j))

graph = [[INF for i in range(n)] for j in range(n)]

while hq:
    dist, vs, vg = heapq.heappop(hq)
    flag = dijkstra(vs, vg, dist)
    if flag == -1:
        break
    else:
        ans += flag
if flag == -1:
    print(-1)
else:
    print(ans)


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

INF = float('inf')
graph = [[INF for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        graph[i][j] = a[i][j]

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(n):
    for j in range(n):
        if graph[i][j] < a[i][j]:
            print(-1)
            exit()

ans = 0

for i in range(n):
    for j in range(i+1, n):
        v = INF
        for k in range(n):
            if k == i or k == j:
                continue
            v = min(v, graph[i][k] + graph[k][j])
        if v != graph[i][j]:
            ans += graph[i][j]

print(ans)

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

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

INF = float('inf')

def dijkstra(s, g, key):
    dist = [INF for i in range(n)]
    dist[s] = 0
    hq2 = [(0, s)]
    while hq2:
        cost, node = heapq.heappop(hq2)
        if cost > dist[node]:
            continue
        for v_next, d_next in enumerate(graph[node]):
            if d_next == INF:
                continue
            d = d_next + cost
            if d < dist[v_next]:
                dist[v_next] = d
                heapq.heappush(hq2, (dist[v_next], v_next))
    if dist[g] > key:
        graph[s][g] = key
        graph[g][s] = key
        return key
    elif dist[g] == key:
        return 0
    else:
        return -1

ans = 0
hq = []
for i in range(n-1):
    for j in range(i+1, n):
        heapq.heappush(hq, (a[i][j], i, j))

graph = [[INF for i in range(n)] for j in range(n)]

while hq:
    dist, vs, vg = heapq.heappop(hq)
    flag = dijkstra(vs, vg, dist)
    if flag == -1:
        break
    else:
        ans += flag
if flag == -1:
    print(-1)
else:
    print(ans)


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

INF = float('inf')
graph = [[INF for i in range(n)] for j in range(n)]

for i in range(n):
    for j in range(n):
        graph[i][j] = a[i][j]

for k in range(n):
    for i in range(n):
        for j in range(n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

for i in range(n):
    for j in range(n):
        if graph[i][j] < a[i][j]:
            print(-1)
            exit()

ans = 0

for i in range(n):
    for j in range(i+1, n):
        v = INF
        for k in range(n):
            if k == i or k == j:
                continue
            v = min(v, graph[i][k] + graph[k][j])
        if v != graph[i][j]:
            ans += graph[i][j]

print(ans)