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

from heapq import *

n = int(input())
A = [list(map(int,input().split())) for _ in range(n)]

def Dijkstra(s,g):
    dist = [1e100]*n
    dist[s] = 0
    pq = [(dist[s],s)]
    heapify(pq)
    while pq:
        d,p = heappop(pq)
        if dist[p] < d:continue
        for nxt,c in path[p].items():
            if dist[nxt] > c + d:
                dist[nxt] = c + d
                heappush(pq,(dist[nxt],nxt))
    return dist[g]

path = [{} for _ in range(n)]
road = []
heapify(road)

for i in range(1,n):
    for j in range(i):
        a = A[i][j]
        heappush(road,(a,j,i))
ans = 0
while road:
    a,i,j = heappop(road)
    D = Dijkstra(i,j)
    if D < a:
        ans = -1
        break
    elif D > a:
        path[i][j] = a
        path[j][i] = a
        ans += a
print(ans)


Fixed submission:
import sys
input = sys.stdin.readline

n = int(input())
A = [list(map(int,input().split())) for _ in range(n)]

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])

wf = WarshallFloyd(n)

for i in range(1,n):
    for j in range(i):
        wf.path(i,j,A[i][j])

wf.build()
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        if A[i][j] > wf.d[i][j]:
            print(-1)
            exit(0)
        flag = 1
        for k in range(n):
            if i != k != j:
                if wf.d[i][j] == wf.d[i][k] + wf.d[k][j]:
                    flag = 0
                    break
        if flag:
            ans += A[i][j]
print(ans)

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

from heapq import *

n = int(input())
A = [list(map(int,input().split())) for _ in range(n)]

def Dijkstra(s,g):
    dist = [1e100]*n
    dist[s] = 0
    pq = [(dist[s],s)]
    heapify(pq)
    while pq:
        d,p = heappop(pq)
        if dist[p] < d:continue
        for nxt,c in path[p].items():
            if dist[nxt] > c + d:
                dist[nxt] = c + d
                heappush(pq,(dist[nxt],nxt))
    return dist[g]

path = [{} for _ in range(n)]
road = []
heapify(road)

for i in range(1,n):
    for j in range(i):
        a = A[i][j]
        heappush(road,(a,j,i))
ans = 0
while road:
    a,i,j = heappop(road)
    D = Dijkstra(i,j)
    if D < a:
        ans = -1
        break
    elif D > a:
        path[i][j] = a
        path[j][i] = a
        ans += a
print(ans)


Fixed submission:
import sys
input = sys.stdin.readline

n = int(input())
A = [list(map(int,input().split())) for _ in range(n)]

class WarshallFloyd:
    def __init__(self,n):
        self.v = n
        self.d = [[1e100]*n for _ in range(n)]
        for i in range(n):
            self.d[i][i] = 0

    def path(self,x,y,c):
        if x == y:
            return False
        self.d[x][y] = c
        self.d[y][x] = c
        return True

    def build(self):
        for k in range(self.v):
            for i in range(self.v):
                for j in range(self.v):
                    self.d[i][j] = min(self.d[i][j], self.d[i][k] + self.d[k][j])

wf = WarshallFloyd(n)

for i in range(1,n):
    for j in range(i):
        wf.path(i,j,A[i][j])

wf.build()
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        if A[i][j] > wf.d[i][j]:
            print(-1)
            exit(0)
        flag = 1
        for k in range(n):
            if i != k != j:
                if wf.d[i][j] == wf.d[i][k] + wf.d[k][j]:
                    flag = 0
                    break
        if flag:
            ans += A[i][j]
print(ans)