Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Fixed submission:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = dict()
    for i in range(N):
        A[i] = dict()
        ain = [int(j) for j in input().split()]
        for j in range(N): A[i][j] = ain[j]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Fixed submission:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(i) for i in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                compare = A[a][k] + A[k][b]
                if Lab > compare:
                    possible = False
                    break
                elif Lab == compare:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)

    return 0
  
if __name__ == "__main__":
    solve()

Fixed submission:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b
  
def solve():
    N = int(single_input())
    A = [list(map(int, line_input())) for i in range(N)]
    for i in range(N):
        A[i][i] = 10 ** 15

    Total = 0
    possible = True
    for c in itertools.combinations(range(N), 2):
        a, b = int(c[0]), int(c[1])
        dist = A[a][b]
        for i in range(N):
            if A[a][i] + A[b][i] == dist: break
            elif A[a][i] + A[b][i] < dist:
                possible = False
                break
        else: Total += dist
        if not possible:
            print(-1)
            break
    else: print(Total)

    return 0
  
if __name__ == "__main__":
    solve()

Fixed submission:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]
for i in range(N):
    A[i][i] = float("inf")
Node = [int(i) for i in range(N)]
Comb = list(itertools.combinations(Node, 2))
 
Total, Possible = 0, True
for c in Comb:
    a = A[c[0]][c[1]]
    for i in range(N):
        if A[c[0]][i] + A[c[1]][i] == a:
            break
        elif A[c[0]][i] + A[c[1]][i] < a:
            Possible = False
            break
    else:
        Total += a
    if not Possible:
        print(-1)
        break
else:
    print(Total)

Fixed submission:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]
Node = [int(i) for i in range(N)]
Comb = list(itertools.combinations(Node, 2))
 
Total = 0
count = 0
while count < N * (N-1) // 2:
    for c in Comb:
        count += 1
        for i in range(N):
            if i!=c[0] and i!=c[1]:
                if A[c[0]][c[1]] == A[c[0]][i] + A[c[1]][i]:
                    break
                elif A[c[0]][c[1]] > A[c[0]][i] + A[c[1]][i]:
                    count = N**2
                    break
        else:
            Total += A[c[0]][c[1]]
                    
if count == N * (N-1) // 2:
    print(Total)
else:
    print(-1)

Fixed submission:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]
Node = [int(i) for i in range(N)]
Comb = list(itertools.combinations(Node, 2))

Possible = True
Total, count = 0, 0
while count < N * (N-1) // 2:
    for c in Comb:
        a, i, j = A[c[0]][c[1]], c[0], c[1]
        count += 1
        MinDist = float("inf")
        for k in range(N):
            if k != i and k != j:
                if a > A[i][k] + A[k][j]:
                    count = N**2
                    break
                else:
                    MinDist = min(MinDist, A[i][k] + A[k][j])
        else:
            Total += (a if MinDist > a else 0)
        
if count == N*(N-1)//2:
    print(Total)
else:
    print(-1)

Fixed submission:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]
Node = [int(i) for i in range(N)]
Comb = list(itertools.combinations(Node, 2))
 
Possible = True
NoNeed = 0
count = 0
while Possible and count < N * (N-1) // 2:
    for c in Comb:
        count += 1
        for i in range(N):
            if i!=c[0] and i!=c[1]:
                if A[c[0]][c[1]] < A[c[0]][i] + A[c[1]][i]:
                    continue
                elif A[c[0]][c[1]] == A[c[0]][i] + A[c[1]][i]:
                    NoNeed += A[c[0]][c[1]]
                    break
                else:
                    Possible = False
                    break
                    
if Possible:
    Total = 0
    for i in range(N):
        Total += sum(A[i])
    Total //= 2
    Total -= NoNeed
    print(Total)
else:
    print(-1)

Fixed submission:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]
Node = [int(i) for i in range(N)]
Comb = list(itertools.combinations(Node, 2))

Possible = True
NoNeed = 0
count = 0
while Possible and count < N * (N-1) // 2:
    for c in Comb:
        a, i, j = A[c[0]][c[1]], c[0], c[1]
        count += 1
        MinDist = float("inf")
        for k in range(N):
            if k != i and k != j:
                MinDist = min(MinDist, A[i][k] + A[k][j])
        if MinDist < a:
            Possible = False
        elif MinDist == a:
            NoNeed += a
        

if Possible:
    Total = 0
    for i in range(N):
        Total += sum(A[i])
    Total //= 2
    Total -= NoNeed
    print(Total)

else:
    print(-1)

Fixed submission:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]
Node = [int(i) for i in range(N)]
Comb = list(itertools.combinations(Node, 2))

Possible = True
NoNeed = 0
count = 0
while Possible and count < N * (N-1) // 2:
    for c in Comb:
        count += 1
        for i in range(N):
            if i!=c[0] and i!=c[1]:
                if A[c[0]][c[1]] < A[c[0]][i] + A[c[1]][i]:
                    continue
                elif A[c[0]][c[1]] == A[c[0]][i] + A[c[1]][i]:
                    NoNeed += A[c[0]][c[1]]
                    break
                else:
                    Possible = False

if Possible:
    Total = 0
    for i in range(N):
        Total += sum(A[i])
    Total //= 2
    Total -= NoNeed
    print(Total)

else:
    print(-1)


Fixed submission:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]

Possible = True
NoNeed = set()
for i in range(N-1):
    if not Possible:
        break
    for j in range(i+1, N):
        if not Possible:
            break
        for k in range(N):
            if not Possible:
                break
            if A[i][j] <= A[i][k]+A[j][k]:
                if k != i and k !=j:
                    if A[i][j] == A[i][k]+A[j][k]:
                        NoNeed |= {(i, j)}
            else:
                Possible = False        

if Possible:
    Total = 0
    for i in range(N):
        Total += sum(A[i])
    Total //= 2
    for a in NoNeed:
        Total -= A[a[0]][a[1]]
    print(Total)
else:
    print(-1)

Fixed submission:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]

Possible = True
NoNeed = set()
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            a, b, c = A[i][j], A[j][k], A[i][k]
            if a+b>=c and b+c>=a and c+a>=b:
                if a+b==c:
                    NoNeed |= {(i, k)}
                elif b+c==a:
                    NoNeed |= {(i, j)}
                elif c+a == b:
                    NoNeed |= {(j, k)}
            else:
                Possible = False
                break 

if Possible:
    Total = 0
    for i in range(N):
        Total += sum(A[i])
    Total //= 2
    for a in NoNeed:
        Total -= A[a[0]][a[1]]
    print(Total)
else:
    print(-1)

Fixed submission:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = [[int(i) for i in input().split()] for j in range(N)]

Possible = True
NoNeed = set()
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            a, b, c = A[i][j], A[j][k], A[i][k]
            if a+b>=c and b+c>=a and c+a>=b:
                if a+b==c:
                    NoNeed |= {(i, k)}
                elif b+c==a:
                    NoNeed |= {(i, j)}
                elif c+a == b:
                    NoNeed |= {(j, k)}
            else:
                Possible = False
                break 

if Possible:
    Total = 0
    for i in range(N-1):
        for j in range(i+1, N):
            if (i, j) in NoNeed:
                continue
            else:
                Total += A[i][j]
    print(Total)
else:
    print(-1)

Fixed submission:
import sys
from itertools import permutations, combinations
  
def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(N)]

    length = 0
    possible = True
    for a, b in combinations(range(N), 2):
        Lab = A[a][b]
        create_pass = True
        for k in range(N):
            if k != a and k != b:
                if Lab >  A[a][k] + A[k][b]:
                    possible = False
                    break
                elif Lab ==  A[a][k] + A[k][b]:
                    create_pass = False
                    break
        if create_pass: length += Lab
        if not possible:
            print(-1)
            break
    else: print(length)
    
    return 0
  
if __name__ == "__main__":
    solve()