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

def main():
    n = int(input())
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    for i in range(n-1):
        que = []
        d = [10**15 for _ in range(n)]
        d[i] = 0
        heappush( que,(0,i) )
        while que:
            p =  heappop(que)
            v = p[1]
            if d[v] < p[0]:
                continue
            for k in range(len(g[v])):
                edge = g[v][k]
                if d[edge[0]] > d[v] + edge[1]:
                    d[edge[0]] = d[v] + edge[1]
                    heappush( que,(d[edge[0]] , edge[0]) )
        if d != a[i]:
            print(-1)
            return
        for j in range(i+1,n):
            que = []
            d = [10**15 for _ in range(n)]
            d[i] = 0
            heappush( que,(0,i) )
            while que:
                p =  heappop(que)
                v = p[1]
                if d[v] < p[0]:
                    continue
                for k in range(len(g[v])):
                    edge = g[v][k]
                    if (edge[0], v) == (i,j) or (edge[0], v) == (j,i):
                        continue
                    if d[edge[0]] > d[v] + edge[1]:
                        d[edge[0]] = d[v] + edge[1]
                        heappush( que,(d[edge[0]] , edge[0]) )
            if d[j] == a[i][j]:
                ans -= a[i][j]
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def main():
    n = int(input())
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    w = []
    for i in range(n):
        que = []
        d = [10**15 for _ in range(n)]
        d[i] = 0
        heappush( que,(0,i) )
        while que:
            p =  heappop(que)
            v = p[1]
            if d[v] < p[0]:
                continue
            for k in range(len(g[v])):
                edge = g[v][k]
                if d[edge[0]] > d[v] + edge[1]:
                    d[edge[0]] = d[v] + edge[1]
                    heappush( que,(d[edge[0]] , edge[0]) )
        w.append(d)
    for i in range(n-1):
        for j in range(i+1,n):
            if w[i][j] < a[i][j]:
                print(-1)
                return
            flag = 0
            for k in range(n):
                if i == k or j == k:
                    continue
                if w[i][k] + w[k][j] == w[i][j]:
                    flag = 1
            if flag:
                ans -= w[i][j]
    print(ans)

if __name__ == "__main__":
    main()

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

def dijkstra(s,n,g):
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while que:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def dijkstra1(s,ss,n,g):
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while que:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if (edge[0], v) == (s,ss) or (edge[0], v) == (ss,s):
                continue
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n = int(input())
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    for i in range(n-1):
        d = dijkstra(i,n,g)
        if d != a[i]:
            print(-1)
            return
        for j in range(i+1,n):
            d = dijkstra1(i,j,n,g)
            if d[j] == a[i][j]:
                ans -= a[i][j]
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def main():
    n = int(input())
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    w = []
    for i in range(n):
        que = []
        d = [10**15 for _ in range(n)]
        d[i] = 0
        heappush( que,(0,i) )
        while que:
            p =  heappop(que)
            v = p[1]
            if d[v] < p[0]:
                continue
            for k in range(len(g[v])):
                edge = g[v][k]
                if d[edge[0]] > d[v] + edge[1]:
                    d[edge[0]] = d[v] + edge[1]
                    heappush( que,(d[edge[0]] , edge[0]) )
        w.append(d)
    for i in range(n-1):
        for j in range(i+1,n):
            if w[i][j] < a[i][j]:
                print(-1)
                return
            flag = 0
            for k in range(n):
                if i == k or j == k:
                    continue
                if w[i][k] + w[k][j] == w[i][j]:
                    flag = 1
            if flag:
                ans -= w[i][j]
    print(ans)

if __name__ == "__main__":
    main()

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

def dijkstra(s,n,g):
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while que:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def dijkstra1(s,ss,n,g):
    que = []
    d = [10**15 for _ in range(n)]
    d[s] = 0
    heappush( que,(0,s) )
    while que:
        p =  heappop(que)
        v = p[1]
        if d[v] < p[0]:
            continue
        for i in range(len(g[v])):
            edge = g[v][i]
            if (edge[0], v) == (s,ss) or (edge[0], v) == (ss,s):
                continue
            if d[edge[0]] > d[v] + edge[1]:
                d[edge[0]] = d[v] + edge[1]
                heappush( que,(d[edge[0]] , edge[0]) )
    return d

def main():
    n = int(input())
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    for i in range(n-1):
        d = dijkstra(i,n,g)
        if d != a[i]:
            print(-1)
            return
        for j in range(i+1,n):
            d = dijkstra1(i,j,n,g)
            if d[j] == a[i][j]:
                ans -= a[i][j]
    print(ans)

if __name__ == "__main__":
    main()

Fixed submission:
import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def main():
    n = int(input())
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    w = []
    for i in range(n):
        que = []
        d = [10**15 for _ in range(n)]
        d[i] = 0
        heappush( que,(0,i) )
        while que:
            p =  heappop(que)
            v = p[1]
            if d[v] < p[0]:
                continue
            for k in range(len(g[v])):
                edge = g[v][k]
                if d[edge[0]] > d[v] + edge[1]:
                    d[edge[0]] = d[v] + edge[1]
                    heappush( que,(d[edge[0]] , edge[0]) )
        w.append(d)
    for i in range(n-1):
        for j in range(i+1,n):
            if w[i][j] < a[i][j]:
                print(-1)
                return
            flag = 0
            for k in range(n):
                if i == k or j == k:
                    continue
                if w[i][k] + w[k][j] == w[i][j]:
                    flag = 1
            if flag:
                ans -= w[i][j]
    print(ans)

if __name__ == "__main__":
    main()