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

for i in r: A[i][i] = float('inf')
possible = True
ans = 0
for i in r :
    for j in range(i+1,N):
        for k in r:
            if A[i][j] < A[i][k] + A[k][j]:
                continue
            elif A[i][j] == A[i][k] + A[k][j]:
                break
            else:
                possible = False
                break
        else:
            ans += A[i][j]
print(ans if possible else -1)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product

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

for i in r: A[i][i] = float('inf')
possible = True
ans = 0
for i in r :
    for j in range(i+1,N):
        for k in r:
            if A[i][j] < A[i][k] + A[k][j]:
                continue
            elif A[i][j] == A[i][k] + A[k][j]:
                break
            else:
                possible = False
            break
        else:
            ans += A[i][j]
print(ans if possible else -1)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product

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

for i in r: A[i][i] = float('inf')
possible = True
ans = 0
for i,j in product(r, r) :
    if j <= i: continue
    for k in r:
        if A[i][j] < A[i][k] + A[k][j]:
            continue
        elif A[i][j] == A[i][k] + A[k][j]:
            break
        else:
            possible = False
        break
    else:
        ans += A[i][j]
print(ans if possible else -1)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product

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

possible = True
ans = 0
for i,j in product(r, r) :
    if j <= i: continue
    for k in r:
        if k == i or k == j:
            continue
        if A[i][j] < A[i][k] + A[k][j]:
            continue
        elif A[i][j] == A[i][k] + A[k][j]:
            break
        else:
            possible = False
        break
    else:
        ans += A[i][j]
print(ans if possible else -1)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product

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

possible = True
ans = 0
for i,j in product(r, r) :
    for k in r:
        if k == i or k == j:
            continue
        if A[i][j] < A[i][k] + A[k][j]:
            continue
        elif A[i][j] == A[i][k] + A[k][j]:
            break
        else:
            possible = False
        break
    else:
        ans += A[i][j]
print(ans//2 if possible else -1)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import product
with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

possible = True
ans = 0
r = range(N)
for i,j in product(r, r) :
    for k in r:
        if k == i or k == j:
            continue
        if A[i][j] < A[i][k] + A[k][j]:
            continue
        elif A[i][j] == A[i][k] + A[k][j]:
            break
        else:
            possible = False
        break
    else:
        ans += A[i][j]
print(ans//2 if possible else -1)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

possible = True
ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            if k == i or k == j:
                continue
            if A[i][j] < A[i][k] + A[k][j]:
                continue
            elif A[i][j] == A[i][k] + A[k][j]:
                break
            else:
                possible = False
                break
        else:
            ans += A[i][j]
print(ans if possible else -1)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

possible = True
ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            if k in (i, j):
                continue
            if A[i][j] < A[i][k] + A[k][j]:
                continue
            elif A[i][j] == A[i][k] + A[k][j]:
                break
            else:
                possible = False
                break
        else:
            ans += A[i][j]
print(ans if possible else -1)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

A = np.array(A, dtype='int64')
possible = True
ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            if k in (i, j):
                continue
            if A[i, j] < A[i, k] + A[k, j]:
                continue
            if A[i, j] == A[i, k] + A[k, j]:
                break
            if A[i, j] > A[i, k] + A[k, j]:
                possible = False
                break
        else:
            ans += A[i, j]
print(ans if possible else -1)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from scipy.sparse.csgraph import dijkstra
from itertools import count

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

A = np.array(A, dtype='int64')
shortcut = dijkstra(A, directed=False)
if not np.array_equal(A, shortcut):
    print(-1)
    exit()

ans = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(N):
            if k in (i, j):
                continue
            if A[i, j] < A[i, k] + A[k, j]:
                continue
            if A[i, j] == A[i, k] + A[k, j]:
                break
        else:
            ans += A[i, j]

print(ans)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from scipy.sparse.csgraph import dijkstra
from itertools import count

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

A = np.array(A, dtype='int64')
shortcut = dijkstra(A, directed=False)
if not np.array_equal(A, shortcut):
    print(-1)
    exit()

for i in count():
    if i == N:
        break
    for j in count(i+1):
        if j == N:
            break
        if A[i, j] == 0:
            continue
        for k in count():
            if k == N:
                break
            if A[i, k] == 0 or A[j, k] == 0:
                continue
            if A[i, j] == A[i, k] + A[k, j]:
                A[i, j] = A[j, i] = 0

print(sum(sum(A))//2)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
from scipy.sparse.csgraph import dijkstra

with open(0) as f:
    N = int(f.readline())
    A = [list(map(int, line.split())) for line in f.readlines()]

A = np.array(A, dtype='int64')
shortcut = dijkstra(A, directed=False)
if not np.array_equal(A, shortcut):
    print(-1)
    exit()

for i in range(N):
    for j in range(i+1,N):
        if A[i, j] == 0:
            continue
        for k in range(N):
            if A[i, k] == 0 or A[j, k] == 0:
                continue
            if A[i, j] == A[i, k] + A[k, j]:
                A[i, j] = A[j, i] = 0

print(sum(sum(A))//2)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
Need = [True] *(N*N)
ans = 0
for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k] + A[k][j]
            if A[i][j] > Aikj:
                ans = -1
            if A[i][j] == Aikj:
                Need[i*N+j] = False

if ans != -1:
    for i in range(N):
        for j in range(i+1,N):
            if Need[i*N+j]:
                ans += A[i][j]
print(ans)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
Need = [[True]*N for _ in range(N)]
ans = 0
for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k] + A[k][j]
            if A[i][j] > Aikj:
                ans = -1
            if A[i][j] == Aikj:
                Need[i][j] = False

if ans != -1:
    for i in range(N):
        for j in range(i+1,N):
            if Need[i][j]:
                ans += A[i][j]
print(ans)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [[(int(x),True) for x in input().split()] for _ in range(N)]

ans = 0
for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k][0] + A[k][j][0]
            if A[i][j][0] > Aikj:
                ans = -1
            if A[i][j][0] == Aikj:
                A[i][j][1] = False

if ans != -1:
    for i in range(N):
        for j in range(i+1,N):
            if A[i][j][1]:
                ans += A[i][j][0]
print(ans)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Runtime Error):
import sys
N = int(input())
A = [[(int(x),True) for x in input().split()] for _ in range(N)]

ans = 0
for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k][0] + A[k][j][0]
            if A[i][j][0] > Aikj:
                ans = -1
            if A[i][j][0] == Aikj:
                A[i][j][1] = False

if ans != -1:
    for i in range(N):
        for j in range(i+1,N):
            if A[i][j][1]:
                ans += A[i][j][0]
print(ans)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Runtime Error):
import sys
N = int(input())
A = [[(int(x),True) for x in input().split()] for _ in range(N)]

for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k][0] + A[k][j][0]
            if A[i][j][0] > Aikj:
                print(-1)
                sys.exit()
            if A[i][j][0] == Aikj:
                A[i][j][1] = False

ans = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i][j][1]:
            ans += A[i][j][0]
print(ans)

Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Runtime Error):
import sys
N = int(input())
A = [[(int(x),True) for x in input().split()] for _ in range(N)]

for k in range(N):
    for i in range(N):
        if i == k: continue
        for j in range(i+1,N):
            if j == k: continue
            Aikj = A[i][k][0] + A[k][j][0]
            if A[i][j][0] > Aikj:
                print(-1)
                sys.exit()
            if A[i][j][0] == Aikj:
                A[i][j][1] = False

ans = 0
for i in range(N):
    for j in range(i+1,N):
        if A[i][j][1]:
            ans += A[i][j][0]
print(ans)
            



Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
road_length = sum(sum(a) for a in A) //2

for k in range(N):
    for i in range(N):
        for j in range(i+1,N):
            if A[i][j] > A[i][k] + A[k][j]:
                print(-1)
                sys.exit()
            if A[i][j] == A[i][k] + A[k][j] and i != k and j != k:
                road_length -= A[i][j]
ans = road_length
print(ans)
            



Fixed submission:
def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()