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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    Ai = A[i]
    for j in range(i):
        Aj = A[j]
        d = INF * 2
        for k in range(N):
            d = min(d, Ai[k] + Aj[k])

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

print(ans)


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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    Ai = A[i]
    for j in range(i):
        d = min(map(sum, zip(Ai, A[j])))

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

print(ans)

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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    for j in range(i):
        d = INF * 2
        for k in range(N):
            d = min(d, A[i][k] + A[k][j])

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

print(ans)


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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    Ai = A[i]
    for j in range(i):
        d = min(map(sum, zip(Ai, A[j])))

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

print(ans)

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

# Warshall-Floyd法
dist = [list(A[i]) for i in range(N)]
via = [[None for i in range(N)] for j in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] >= d:
                dist[i][j] = d
                if i != k and j != k:
                    via[i][j] = k

ans = 0
for i in range(N):
    for j in range(i):
        if dist[i][j] < A[i][j]:
            ans = -1
            break

        if via[i][j] == None:
            ans += dist[i][j]

    if ans == -1:
        break

print(ans)


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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    Ai = A[i]
    for j in range(i):
        d = min(map(sum, zip(Ai, A[j])))

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

print(ans)

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

adj = [{} for i in range(N)]
for i in range(N):
    for j in range(i + 1, N):
        adj[i][j] = A[i][j]
        adj[j][i] = A[j][i]

import heapq

def Dijkstra(numV, v_st):

    cost = [float('inf') for i in range(numV)]
    cost[v_st] = 0
    num = [0 for i in range(numV)]

    pq = []
    heapq.heappush(pq, (0, v_st))

    while pq:
        c_min, v_now = heapq.heappop(pq)

        if cost[v_now] < c_min:
            continue

        for v, c in adj[v_now].items():
            if cost[v_now] + c < cost[v]:
                cost[v] = cost[v_now] + c
                num[v] = num[v_now] + 1
                heapq.heappush(pq, (cost[v], v))
            elif cost[v_now] + c == cost[v]:
                if num[v] == 1:
                    del adj[v_st][v]
                    del adj[v][v_st]
                elif num[v_now] + 1 == 1:
                    del adj[v_now][v]
                    del adj[v][v_now]
                num[v] = max(num[v], num[v_now] + 1)

    return cost

dist = [[] for i in range(N)]
for i in range(N):
    dist[i] = Dijkstra(N, i)

ans = sum(sum(adj[i].values()) for i in range(N)) // 2
for i in range(N):
    for j in range(N):
        if dist[i][j] < A[i][j]:
            ans = -1
            break
    if ans == -1:
        break

print(ans)


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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    Ai = A[i]
    for j in range(i):
        d = min(map(sum, zip(Ai, A[j])))

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

print(ans)

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

import heapq

def Dijkstra(numV, v_st):

    cost = [float('inf') for i in range(numV)]
    cost[v_st] = 0
    num = [0 for i in range(numV)]

    pq = []
    heapq.heappush(pq, (0, v_st))

    while pq:
        c_min, v_now = heapq.heappop(pq)

        if cost[v_now] < c_min:
            continue

        for v in range(numV):
            if v == v_now:
                continue
            if cost[v_now] + adj[v_now][v] < cost[v]:
                cost[v] = cost[v_now] + adj[v_now][v]
                num[v] = num[v_now] + 1
                heapq.heappush(pq, (cost[v], v))
            elif cost[v_now] + adj[v_now][v] == cost[v]:
                num[v] = max(num[v], num[v_now] + 1)

    return (cost, num)


dist = [[] for i in range(N)]
num = [[] for i in range(N)]
for i in range(N):
    (dist[i], num[i]) = Dijkstra(N, i)

ans = sum(sum(adj[i]) for i in range(N)) // 2
for i in range(N):
    for j in range(i + 1, N):

        if dist[i][j] < adj[i][j]:
            ans = -1
            break

        if num[i][j] > 1:
            if dist[i][j] == adj[i][j]:
                ans -= dist[i][j]

    if ans == -1:
        break

print(ans)


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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    Ai = A[i]
    for j in range(i):
        d = min(map(sum, zip(Ai, A[j])))

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

print(ans)

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

import heapq

def Dijkstra(numV, v_st):

    cost = [float('inf') for i in range(numV)]
    cost[v_st] = 0
    num = [0 for i in range(numV)]

    pq = []
    heapq.heappush(pq, (0, v_st))

    while pq:
        c_min, v_now = heapq.heappop(pq)

        if cost[v_now] < c_min:
            continue

        for v in range(numV):
            if v == v_now:
                continue
            if cost[v_now] + adj[v_now][v] < cost[v]:
                cost[v] = cost[v_now] + adj[v_now][v]
                num[v] = num[v_now] + 1
                heapq.heappush(pq, (cost[v], v))
            elif cost[v_now] + adj[v_now][v] == cost[v]:
                num[v] = max(num[v], num[v_now] + 1)

    return (cost, num)


dist = [[] for i in range(N)]
num = [[] for i in range(N)]
for i in range(N):
    (dist[i], num[i]) = Dijkstra(N, i)

ans = sum(sum(adj[i]) for i in range(N)) // 2
for i in range(N):
    for j in range(i + 1, N):

        if dist[i][j] < adj[i][j]:
            ans = -1
            break

        if num[i][j] > 1:
            if dist[i][j] == adj[i][j]:
                ans -= dist[i][j]

    if ans == -1:
        break

print(ans)


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

INF = 10 ** 9 + 1
for i in range(N):
    A[i][i] = INF

ans = 0
for i in range(N):
    Ai = A[i]
    for j in range(i):
        d = min(map(sum, zip(Ai, A[j])))

        if A[i][j] > d:
            print('-1')
            exit()
        elif A[i][j] < d:
            ans += A[i][j]

print(ans)