Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        l = []
        s = d[i][j]
        for k in range(n):
            if k == i or k == j:
                continue
            dist = d[i][k] + d[k][j]
            if dist == s:
                ans -= s
                break
            d[i][j] = min(d[i][j], dist)
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)

Fixed submission:
from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        l = []
        s = d[i][j]
        for k in range(n):
            if k == i or k == j:
                continue
            dist = d[i][k] + d[k][j]
            if dist == s:
                ans -= s
                break
            d[i][j] = min(d[i][j], dist)
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        l = []
        for k in range(n):
            dist = d[i][k] + d[k][j]
            l.append(dist)
            d[i][j] = min(d[i][j], dist)
        for m in Counter(l).most_common():
            if m[1] >= 3:
                ans -= m[0]
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)

Fixed submission:
from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        l = []
        s = d[i][j]
        for k in range(n):
            if k == i or k == j:
                continue
            dist = d[i][k] + d[k][j]
            if dist == s:
                ans -= s
                break
            d[i][j] = min(d[i][j], dist)
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(n):
        l = []
        if i > j:
            continue
        for k in range(n):
            if i != j:
                l.append(d[i][k] + d[k][j])
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        for m in Counter(l).most_common():
            if m[1] >= 3:
                ans -= m[0]
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)

Fixed submission:
from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        l = []
        s = d[i][j]
        for k in range(n):
            if k == i or k == j:
                continue
            dist = d[i][k] + d[k][j]
            if dist == s:
                ans -= s
                break
            d[i][j] = min(d[i][j], dist)
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(n):
        l = []
        for k in range(n):
            if i != j:
                l.append(d[i][k] + d[k][j])
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        for m in Counter(l).most_common():
            if m[1] >= 3:
                ans -= m[0]
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
for i in range(n):
    ans += sum(a[i])
print(ans // 2)

Fixed submission:
from collections import Counter

n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
d = [x[:] for x in a]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        l = []
        s = d[i][j]
        for k in range(n):
            if k == i or k == j:
                continue
            dist = d[i][k] + d[k][j]
            if dist == s:
                ans -= s
                break
            d[i][j] = min(d[i][j], dist)
for i in range(n):
    if a[i] != d[i]:
        print(-1)
        exit()
an = 0
for i in range(n):
    an += sum(a[i])
print(an // 2 + ans)