Buggy python submission (verdict: Time Limit Exceeded):
from heapq import *
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n=int(input())
aa=LLI(n)

def main():
    ans=sum(sum(ar) for ar in aa)//2
    for w in range(n):
        for u in range(n):
            if u==w:continue
            aau=aa[u]
            for v in range(u):
                if v==w:continue
                d=aau[w]+aa[w][v]
                if d<aau[v]:
                    print(-1)
                    exit()
                if d==aau[v]:
                    ans-=d
    print(ans)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n=int(input())
aa=LLI(n)

def main():
    ans=sum(sum(ar) for ar in aa)//2
    fin=set()
    for w in range(n):
        aaw=aa[w]
        for u in range(n):
            if u==w:continue
            aau=aa[u]
            for v in range(u):
                if v==w:continue
                d=aau[w]+aaw[v]
                if d<aau[v]:
                    print(-1)
                    exit()
                if d==aau[v] and (u,v) not in fin:
                    ans-=d
                    fin.add((u,v))
    print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import *
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class UnionFind:
    def __init__(self, n):
        self.state = [-1] * n
        # self.size_table = [1] * n
        # cntはグループ数
        # self.cnt = n

    def root(self, u):
        v = self.state[u]
        if v < 0: return u
        self.state[u] = res = self.root(v)
        return res

    def merge(self, u, v):
        ru = self.root(u)
        rv = self.root(v)
        if ru == rv: return
        du = self.state[ru]
        dv = self.state[rv]
        if du > dv: ru, rv = rv, ru
        if du == dv: self.state[ru] -= 1
        self.state[rv] = ru
        return

def main():
    inf = 10 ** 12
    n = int(input())
    aa = LLI(n)
    #二点間の距離をヒープに記録
    hp = []
    for v in range(n):
        for u in range(v):
            heappush(hp, [aa[u][v], u, v])

    #距離の短い順に取り出して処理
    uf=UnionFind(n)
    ans = 0
    first = [True] * n
    to = defaultdict(list)
    while hp:
        d, u, v = heappop(hp)
        #頂点が非連結のときはそのまま辺をはる
        if uf.root(u)!=uf.root(v):
            to[u].append([v, d])
            to[v].append([u, d])
            ans += d
            uf.merge(u,v)
        #頂点が連結のときはダイクストラで現在の距離を求める
        else:
            vis=[False]*n
            hp2=[]
            heappush(hp2,[0,u])
            while hp2:
                dtou,w=heappop(hp2)
                #現在の距離が作りたい距離より短いことが確定したときは辺を張る
                if dtou>d:
                    to[u].append([v, d])
                    to[v].append([u, d])
                    ans += d
                    break
                if w==v:
                    #現在の距離が作りたい距離より短いときは失敗
                    if dtou<d:
                        print(-1)
                        exit()
                    # 現在の距離が作りたい距離と同じときは何もしない
                    break
                if vis[w]:continue
                vis[w]=True
                for cw,cd in to[w]:
                    if vis[cw]:continue
                    heappush(hp2,[dtou+cd,cw])

    print(ans)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n=int(input())
aa=LLI(n)

def main():
    ans=sum(sum(ar) for ar in aa)//2
    fin=set()
    for w in range(n):
        aaw=aa[w]
        for u in range(n):
            if u==w:continue
            aau=aa[u]
            for v in range(u):
                if v==w:continue
                d=aau[w]+aaw[v]
                if d<aau[v]:
                    print(-1)
                    exit()
                if d==aau[v] and (u,v) not in fin:
                    ans-=d
                    fin.add((u,v))
    print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import *
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 12
    n = int(input())
    aa = LLI(n)
    #二点間の距離をヒープに記録
    hp = []
    for v in range(n):
        for u in range(v):
            heappush(hp, [aa[u][v], u, v])
    #距離の短い順に取り出して処理
    ans = 0
    first = [True] * n
    to = defaultdict(list)
    while hp:
        d, u, v = heappop(hp)
        #どちらかの頂点が初登場のときはそのまま辺をはる
        if first[u] or first[v]:
            to[u].append([v, d])
            to[v].append([u, d])
            ans += d
            first[u], first[v] = False, False
        #両頂点共に登場済みのときはダイクストラで現在の距離を求める
        else:
            vis=[False]*n
            hp2=[]
            heappush(hp2,[0,u])
            while hp2:
                dtou,w=heappop(hp2)
                #現在の距離が作りたい距離より短いことが確定したときは辺を張る
                if dtou>d:
                    to[u].append([v, d])
                    to[v].append([u, d])
                    ans += d
                    break
                if w==v:
                    #現在の距離が作りたい距離より短いときは失敗
                    if dtou<d:
                        print(-1)
                        exit()
                    # 現在の距離が作りたい距離と同じときは何もしない
                    break
                if vis[w]:continue
                vis[w]=True
                for cw,cd in to[w]:
                    if vis[cw]:continue
                    heappush(hp2,[dtou+cd,cw])
            else:
                #uvが非連結のときは辺を張る
                to[u].append([v, d])
                to[v].append([u, d])
                ans += d

    print(ans)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n=int(input())
aa=LLI(n)

def main():
    ans=sum(sum(ar) for ar in aa)//2
    fin=set()
    for w in range(n):
        aaw=aa[w]
        for u in range(n):
            if u==w:continue
            aau=aa[u]
            for v in range(u):
                if v==w:continue
                d=aau[w]+aaw[v]
                if d<aau[v]:
                    print(-1)
                    exit()
                if d==aau[v] and (u,v) not in fin:
                    ans-=d
                    fin.add((u,v))
    print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import *
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 12
    n = int(input())
    aa = LLI(n)
    #二点間の距離をヒープに記録
    hp = []
    for v in range(n):
        for u in range(v):
            heappush(hp, [aa[u][v], u, v])
    #距離の短い順に取り出して処理
    ans = 0
    first = [True] * n
    to = defaultdict(list)
    while hp:
        d, u, v = heappop(hp)
        #どちらかの頂点が初登場のときはそのまま辺をはる
        if first[u] or first[v]:
            to[u].append([v, d])
            to[v].append([u, d])
            ans += d
            first[u], first[v] = False, False
        #両頂点共に登場済みのときはダイクストラで現在の距離を求める
        else:
            vis=[False]*n
            hp2=[]
            heappush(hp2,[0,u])
            while hp2:
                dtou,w=heappop(hp2)
                #現在の距離が作りたい距離より短いことが確定したときは辺を張る
                if dtou>d:
                    to[u].append([v, d])
                    to[v].append([u, d])
                    ans += d
                    break
                if w==v:
                    #現在の距離が作りたい距離より短いときは失敗
                    if dtou<d:
                        print(-1)
                        exit()
                    # 現在の距離が作りたい距離と同じときは何もしない
                    break
                if vis[w]:continue
                vis[w]=True
                for cw,cd in to[w]:
                    if vis[cw]:continue
                    heappush(hp2,[dtou+cd,cw])
            else:
                #uvが非連結のときは辺を張る
                to[u].append([v, d])
                to[v].append([u, d])
                ans += d

    print(ans)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n=int(input())
aa=LLI(n)

def main():
    ans=sum(sum(ar) for ar in aa)//2
    fin=set()
    for w in range(n):
        aaw=aa[w]
        for u in range(n):
            if u==w:continue
            aau=aa[u]
            for v in range(u):
                if v==w:continue
                d=aau[w]+aaw[v]
                if d<aau[v]:
                    print(-1)
                    exit()
                if d==aau[v] and (u,v) not in fin:
                    ans-=d
                    fin.add((u,v))
    print(ans)

main()

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import *
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    inf = 10 ** 12
    n = int(input())
    aa = LLI(n)
    hp = []
    for v in range(n):
        for u in range(v):
            heappush(hp, [aa[u][v], u, v])
    ans = 0
    first = [True] * n
    bb = [[inf] * n for _ in range(n)]
    for i in range(n):
        bb[i][i] = 0
    while hp:
        d, u, v = heappop(hp)
        if first[u] or first[v]:
            bb[u][v] = bb[v][u] = d
            ans += d
            first[u], first[v] = False, False
        else:
            min_d = inf
            for w in range(n):
                duv = bb[u][w] + bb[w][v]
                if duv < min_d: min_d = duv
            if d < min_d:
                bb[u][v] = bb[v][u] = d
                ans += d
            elif d > min_d:
                print(-1)
                exit()
    #p2D(bb)
    print(ans)

main()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n=int(input())
aa=LLI(n)

def main():
    ans=sum(sum(ar) for ar in aa)//2
    fin=set()
    for w in range(n):
        aaw=aa[w]
        for u in range(n):
            if u==w:continue
            aau=aa[u]
            for v in range(u):
                if v==w:continue
                d=aau[w]+aaw[v]
                if d<aau[v]:
                    print(-1)
                    exit()
                if d==aau[v] and (u,v) not in fin:
                    ans-=d
                    fin.add((u,v))
    print(ans)

main()