Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
input = sys.stdin.readline


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dist = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0
edges = []
for i in range(N-1):
    for j in range(i+1, N):
        edges.append((A[i][j], i, j))
edges.sort()
edges = deque(edges)
ans = 0
while edges:
    d, u, v = edges.popleft()
    if d > dist[u][v]:
        ans = -1
        break
    if d < dist[u][v]:
        ans += d
        for i in range(N-1):
            for j in range(i+1, N):
                ndist = min(dist[i][j], dist[i][u] + d + dist[v][j], dist[i][v] + d + dist[u][j])
                dist[i][j] = dist[j][i] = ndist
print(ans)


Fixed submission:
from copy import deepcopy
import sys
input = sys.stdin.readline


def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dist = deepcopy(A)
floyd_warshall(dist)
edges = []
for u in range(N-1):
    for v in range(u+1, N):
        edges.append((A[u][v], u, v))
edges.sort()
ans = 0
for d, u, v in edges:
    if dist[u][v] < d:
        ans = -1
        break
    ok = False
    for w in range(N):
        if w == u or w == v:
            continue
        if dist[u][w] + dist[w][v] == dist[u][v]:
            ok = True
            break
    if not ok:
        ans += d
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dist = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0
edges = []
for i in range(N-1):
    for j in range(i+1, N):
        edges.append((A[i][j], i, j))
edges.sort(reverse=True)
ans = 0
while edges:
    d, u, v = edges.pop()
    if d > dist[u][v]:
        ans = -1
        break
    if d < dist[u][v]:
        ans += d
        for i in range(N-1):
            for j in range(i+1, N):
                ndist = min(dist[i][j], dist[i][u] + d + dist[v][j], dist[i][v] + d + dist[u][j])
                dist[i][j] = dist[j][i] = ndist
print(ans)


Fixed submission:
from copy import deepcopy
import sys
input = sys.stdin.readline


def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dist = deepcopy(A)
floyd_warshall(dist)
edges = []
for u in range(N-1):
    for v in range(u+1, N):
        edges.append((A[u][v], u, v))
edges.sort()
ans = 0
for d, u, v in edges:
    if dist[u][v] < d:
        ans = -1
        break
    ok = False
    for w in range(N):
        if w == u or w == v:
            continue
        if dist[u][w] + dist[w][v] == dist[u][v]:
            ok = True
            break
    if not ok:
        ans += d
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop
import sys
input = sys.stdin.readline


def dijkstra(edges, size, source):
    distance = [float('inf')] * size
    distance[source] = 0
    visited = [False] * size
    pq = []
    heappush(pq, (0, source))
    while pq:
        dist_v, v = heappop(pq)
        visited[v] = True
        for u, weight in edges[v]:
            if not visited[u]:
                new_dist = dist_v + weight
                if distance[u] > new_dist:
                    distance[u] = new_dist
                    heappush(pq, (new_dist, u))
    return distance


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
G = [[] for _ in range(N)]
edges = []
for i in range(N-1):
    for j in range(i+1, N):
        edges.append((A[i][j], i, j))
edges.sort(reverse=True)
ans = 0
while edges:
    d, u, v = edges.pop()
    dist = dijkstra(G, N, u)
    if d > dist[v]:
        ans = -1
        break
    if d < dist[v]:
        ans += d
        G[u].append((v, d))
        G[v].append((u, d))
print(ans)


Fixed submission:
from copy import deepcopy
import sys
input = sys.stdin.readline


def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dist = deepcopy(A)
floyd_warshall(dist)
edges = []
for u in range(N-1):
    for v in range(u+1, N):
        edges.append((A[u][v], u, v))
edges.sort()
ans = 0
for d, u, v in edges:
    if dist[u][v] < d:
        ans = -1
        break
    ok = False
    for w in range(N):
        if w == u or w == v:
            continue
        if dist[u][w] + dist[w][v] == dist[u][v]:
            ok = True
            break
    if not ok:
        ans += d
print(ans)