Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
# 小さい順に調べていく
roads = []
for i in range(n-1):
    for j in range(i+1, n):
        roads.append((A[i][j], i, j))
roads = sorted(roads)

INF = 10**9*1
AD = [[INF]*n for _ in range(n)]
G = [[] for _ in range(n)]
edges = set()
from collections import deque
ok = True
ans = 0
for a, s, e in roads:
    # s to e
    q = deque([[s, 0]])
    visited = [INF] * n
    visited[s] = 0
    while q:
        node, dist = q.popleft()
        if node == e:
            # sからeにたどり着いて
            if dist == a:
                # あたえられた距離と同じならばOK
                break
            elif dist < a:
                # あたえられた距離より小さいならばaは最短距離じゃないNG
                ok = False
                break
        
        for nn, cost in G[node]:
            if dist+cost < visited[nn]:
                visited[nn] = dist+cost
                q.append([nn, dist+cost])
    else:
        # sからeにたどり着けなかったら最短距離確定
        AD[s][e] = a
        G[s].append((e, a))
        G[e].append((s, a))
        ans += a
    if not ok:
        break

print(ans if ok else -1)

Fixed submission:
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
INF = 10**9 + 1
dp = [[INF]*n for _ in range(n)]

# コスト登録
for i, line in enumerate(A):
    for j, a in enumerate(line):
        dp[i][j] = a

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        d = dp[i][j]
        if d < A[i][j]:
            ans = -1
            break
        else:
            for k in range(n):
                if k == i or k == j:
                    continue
                if dp[i][k] + dp[k][j] == d:
                    break
            else:
                ans += d
    if ans == -1:
        break
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
# 小さい順に調べていく
roads = []
for i in range(n-1):
    for j in range(i+1, n):
        roads.append((A[i][j], i, j))
roads = sorted(roads)

INF = 10**9*1
AD = [[INF]*n for _ in range(n)]
G = [[] for _ in range(n)]
edges = set()
from collections import deque
ans = 0
for a, s, e in roads:
    # s to e
    q = deque([[s, 0]])
    visited = [INF] * n
    visited[s] = 0
    while q:
        node, dist = q.popleft()
        if node == e:
            # sからeにたどり着いて
            if dist == a:
                # あたえられた距離と同じならばOK
                break
            elif dist < a:
                # あたえられた距離より小さいならばaは最短距離じゃないNG
                ans = -1
                break
        
        for nn, cost in G[node]:
            if dist+cost < visited[nn]:
                visited[nn] = dist+cost
                q.append([nn, dist+cost])
    else:
        # sからeにたどり着けなかったら最短距離確定
        AD[s][e] = a
        G[s].append((e, a))
        G[e].append((s, a))
        edges.add((a, s, e))
    if ans == - 1:
        break

if ans == -1:
    print(ans)
else:
    for a, s, e in edges:
        ans += a
    print(ans)


Fixed submission:
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
INF = 10**9 + 1
dp = [[INF]*n for _ in range(n)]

# コスト登録
for i, line in enumerate(A):
    for j, a in enumerate(line):
        dp[i][j] = a

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        d = dp[i][j]
        if d < A[i][j]:
            ans = -1
            break
        else:
            for k in range(n):
                if k == i or k == j:
                    continue
                if dp[i][k] + dp[k][j] == d:
                    break
            else:
                ans += d
    if ans == -1:
        break
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
# 小さい順に調べていく
from heapq import heappop, heappush
heap = []
for i in range(n-1):
    for j in range(i+1, n):
        a = A[i][j]
        heappush(heap, (a, i, j))

G = [[] for _ in range(n)]
edges = set()
from collections import deque
ans = 0
while heap:
    # s to e
    a, s, e = heappop(heap)
    q = deque([[s, 0]])
    visited = [10**9+1] * n
    visited[s] = 0
    while q:
        node, dist = q.popleft()

        if node == e:
            if dist == a:
                # ok
                break
            elif dist < a:
                ans = -1
                break
        
        for nn, cost in G[node]:
            if dist+cost < visited[nn]:
                visited[nn] = dist+cost
                q.append([nn, dist+cost])
    else:
        # sからeにたどり着けなかったら枝を足す
        G[s].append((e, a))
        G[e].append((s, a))
        edges.add((a, s, e))
    if ans == - 1:
        break

if ans == -1:
    print(ans)
else:
    for a, s, e in edges:
        ans += a
    print(ans)


Fixed submission:
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
INF = 10**9 + 1
dp = [[INF]*n for _ in range(n)]

# コスト登録
for i, line in enumerate(A):
    for j, a in enumerate(line):
        dp[i][j] = a

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        d = dp[i][j]
        if d < A[i][j]:
            ans = -1
            break
        else:
            for k in range(n):
                if k == i or k == j:
                    continue
                if dp[i][k] + dp[k][j] == d:
                    break
            else:
                ans += d
    if ans == -1:
        break
print(ans)