Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = []
    d = []
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(i+1, N):
            if Ai[j] > 0:
                d.append((Ai[j], i, j))
    d.sort(key=lambda x: x[0])


    def wf(dist):
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist


    ok = len(d)+1
    ng = 0
    mid = len(d)
    while ok - ng > 1:
        dist = [[10 ** 10 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            dist[i][i] = 0
        for x, i, j in d[:mid]:
            dist[i][j] = x
            dist[j][i] = x
        if wf(dist) == A:
            ok = mid
        else:
            ng = mid
            if ng == len(d):
                print(-1)
                exit()
        mid = (ok+ng)//2

    ans = 0
    for i in range(ok):
        ans += d[i][0]
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N = int(input())
    A = []
    dist = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(N):
            dist[i][j] = Ai[j]

    def wf(dist):
        need = [[1 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        print(-1)
                        exit()
                    elif dist[i][j] == dist[i][k] + dist[k][j]:
                        if i != k and j != k:
                            need[i][j] = 0
                            need[j][i] = 0
        return need

    need = wf(dist)
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += need[i][j] * dist[i][j]
    print(ans)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = []
    d = []
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(i+1, N):
            if Ai[j] > 0:
                d.append((Ai[j], i, j))
    d.sort(key=lambda x: x[0])


    def wf(dist):
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist


    ok = len(d)+1
    ng = 0
    mid = (ok+ng)//2
    while ok - ng > 1:
        dist = [[10 ** 10 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            dist[i][i] = 0
        for x, i, j in d[:mid]:
            dist[i][j] = x
            dist[j][i] = x
        if wf(dist) == A:
            ok = mid
        else:
            ng = mid
            if ng == len(d):
                print(-1)
                exit()
        mid = (ok+ng)//2

    ans = 0
    for i in range(ok):
        ans += d[i][0]
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
def main():
    N = int(input())
    A = []
    dist = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(N):
            dist[i][j] = Ai[j]

    def wf(dist):
        need = [[1 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        print(-1)
                        exit()
                    elif dist[i][j] == dist[i][k] + dist[k][j]:
                        if i != k and j != k:
                            need[i][j] = 0
                            need[j][i] = 0
        return need

    need = wf(dist)
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += need[i][j] * dist[i][j]
    print(ans)


if __name__ == '__main__':
    main()