CodeEff/ECCO huggingface dataset:
# Original solution
N=int(eval(input()))
dist=[list(map(int,input().split())) for i in range(N)]
ans=sum([sum(dist[i]) for i in range(N)])
ans//=2
was=set()
for i in range(N):
    if ans<0:break
    for j in range(i+1,N):
        if ans<0:break
        for k in range(j+1,N):
            a,b,c=dist[i][j],dist[i][k],dist[j][k]
            if b<a and c<a:
                M=a
                S=b+c
                check=(i,j)
            elif a<b and c<b:
                M=b
                S=a+c
                check=(i,k)
            elif a<c and b<c:
                M=c
                S=a+b
                check=(j,k)
            else:continue
            if S==M:
                if check in was:continue
                ans-=M
                was|={check,}
            elif S<M:
                ans=-1*float('inf')
                break
if ans<0:ans=-1
print(ans)

# Optimized solution
import sys
input=sys.stdin.readline
N=int(eval(input()))
dist=[list(map(int,input().split())) for i in range(N)]
ans=sum([sum(dist[i]) for i in range(N)])
for i in range(N):
    dist[i][i]=float('inf')
ans//=2
def main(ans):
    for i in range(N):
        for j in range(i+1,N):
            Min=min(list(map(sum,list(zip(dist[i],dist[j])))))
            if Min<dist[i][j]:
                return -1
            if Min==dist[i][j]:
                ans-=dist[i][j] 
    return ans
print((main(ans)))
# Original solution
n = int(eval(input()))
A = [list(map(int, input().split())) for _ in range(n)]

def warshal_floyd(d):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j] = min(d[i][j], d[i][k]+d[k][j])
  return d

import copy
B = copy.deepcopy(A)
B = warshal_floyd(B)

ans = 0
for i in range(n):
    for j in range(n):
        if B[i][j] < A[i][j]:
            print((-1))
            exit()
        else:
            for k in range(n):
                if k == i or k == j:
                    continue
                if B[i][j] == B[i][k] + B[k][j]:
                    break
            else:
                ans += A[i][j]
ans //=2
print(ans)

# Optimized solution
def main():
    n = int(eval(input()))
    d = [list(map(int, input().split())) for _ in range(n)]

    ans = 0
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            flag = True
            for k in range(n):
                if k == i or k == j:
                    continue
                if d[i][j] > d[i][k]+d[k][j]:
                    print((-1))
                    exit()
                elif d[i][j] == d[i][k]+d[k][j]:
                    flag = False
                else:
                    pass
            if flag:
                ans += d[i][j]
    #print(ans)
    print((ans//2))

if __name__ == '__main__':
    main()
# Original solution
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import heapq
    n = int(readline())
    dist = [[INF] * n for _ in range(n)]
    hq = []
    table = [[0] * n for _ in range(n)]

    for i in range(n):
        a = list(map(int, readline().split()))
        for j in range(i + 1, n):
            hq.append((a[j], i, j))
            table[i][j] = a[j]

    for i in range(n):
        dist[i][i] = 0

    heapq.heapify(hq)
    ans = 0
    while hq:
        cost, u, v = heapq.heappop(hq)
        cur = dist[u][v]
        if cur > cost:
            ans += cost
            dist[u][v] = cost
            for i in range(n):
                dist[i][v] = min(dist[i][v], dist[i][u] + cost)
                dist[i][u] = min(dist[i][u], dist[i][v] + cost)
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][u] + dist[u][j], dist[i][v] + dist[v][j])

    for i in range(n):
        for j in range(i + 1, n):
            if dist[i][j] != table[i][j]:
                print((-1))
                sys.exit()

    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    import heapq
    n = int(readline())
    dist = [[INF] * n for _ in range(n)]
    hq = []
    table = [[0] * n for _ in range(n)]

    for i in range(n):
        a = list(map(int, readline().split()))
        for j in range(i + 1, n):
            hq.append((a[j], i, j))
            table[i][j] = a[j]
            dist[i][j] = a[j]
            dist[j][i] = a[j]

    for i in range(n):
        dist[i][i] = 0

    for i in range(n):
        for j in range(n):
            for k in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    dist[j][i] = dist[i][j]

    for i in range(n):
        for j in range(i + 1, n):
            if dist[i][j] != table[i][j]:
                print((-1))
                sys.exit()

    ans = 0
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(n):
                if k != i and k!= j:
                    if dist[i][j] == dist[i][k] + dist[k][j]:
                        break
            else:
                ans += dist[i][j]

    print(ans)


if __name__ == '__main__':
    main()
# Original solution

n = int(eval(input()))
a = [list(map(int, input().split())) for _ in range(n)]
#print(a)

for k in range(n-1,-1,-1):
    for i in range(n-1,-1,-1):
        for j in range(n-1,-1,-1):            
            #print(k,i,j,a)
            if (i==j or k==i or k==j):
                continue
            if (a[i][k]!=-1 and a[k][j]!=-1 and a[i][j] == a[i][k]+a[k][j]):
                a[i][j] = -1
            elif (a[i][k]!=-1 and a[k][j]!=-1 and a[i][j] > a[i][k]+a[k][j]):
                print((-1))
                exit()
            
#print(a)

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

# Optimized solution
import sys
input = sys.stdin.readline

def main():
    n = int(eval(input()))
    a = [list(map(int, input().split())) for _ in range(n)]
    #print(a)

    for k in range(n-1,-1,-1):
        for i in range(n-1,-1,-1):
            for j in range(n-1,-1,-1):            
                #print(k,i,j,a)
                if (i==j or k==i or k==j):
                    continue
                if (a[i][k]!=-1 and a[k][j]!=-1 and a[i][j] == a[i][k]+a[k][j]):
                    a[i][j] = -1
                elif (a[i][k]!=-1 and a[k][j]!=-1 and a[i][j] > a[i][k]+a[k][j]):
                    print((-1))
                    exit()
            
    #print(a)

    ans = 0
    for i in range(0,n-1):
        for j in range(i,n):
            if (a[i][j]!=-1):
                ans += a[i][j]
    print(ans)
    
if __name__=="__main__":
    main()
# Original solution
N = int(eval(input()))
A,B,Ans = [],[],0
for i in range(N):
    x = list(map(int,input().split()))
    A.append(x.copy())
    B.append(x.copy())

for k in range(N):
    for i in range(N):
        for j in range(N):
            B[i][j] = min(B[i][j],B[i][k]+ B[k][j])

if A!=B:
    print((-1))
else:
    for i in range(N):
        for j in range(i+1,N):
            exists = True
            for k in range(N):
                if k not in (i,j) and B[i][j]==B[i][k]+B[k][j]:
                    exists = False                    
            if exists:
                Ans += B[i][j]
    print(Ans)



# Optimized solution
N = int(eval(input()))
A,B,Ans = [],[],0
for i in range(N):
    x = list(map(int,input().split()))
    A.append(x[:])
    B.append(x[:])

for k in range(N):
    for i in range(N):
        for j in range(N):
            B[i][j] = min(B[i][j],B[i][k]+ B[k][j])

if A!=B:
    print((-1))
else:
    for i in range(N):
        for j in range(i+1,N):
            exists = True
            for k in range(N):
                if k not in (i,j) and B[i][j]==B[i][k]+B[k][j]:
                    exists = False                    
            if exists:
                Ans += B[i][j]
    print(Ans)
# Original solution
from heapq import heappush, heappop

def prim_heap(edges, n):
    visited = [False] * n
    heap = []
    start = 0
    for e in edges[start]:
        heappush(heap, e)
    visited[start] = True

    res = 0
    while heap:
        cost, v = heappop(heap)
        if visited[v]:
            continue
        visited[v] = True
        res += cost
        for c,u in edges[v]:
            if visited[u]:
                continue
            heappush(heap, (c,u))
    # print(visited)
    return res if sum(visited) == n else -1

def warshall(d, n):
    e = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # print(d[i][k], d[k][j], d[i][j])
                if i == k or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    e[i][k] = 0
                    e[k][j] = 0
                    e[k][i] = 0
                    e[j][k] = 0
                if d[i][k] + d[k][j] == d[i][j]:
                    # print(d[i][k], d[k][j], d[i][j], i,j,k)
                    e[i][j] = 0
                    e[j][i] = 0
    return e
    
import copy
n = int(eval(input()))
edges = []

graph = [list(map(int, input().split())) for i in range(n)]
e = warshall(graph, n)
# print(e)
edge_list = [[] for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j] > 0:
            edge_list[i].append((e[i][j], j))
        if j > i and e[i][j]:
            ans += e[i][j]

print((ans if prim_heap(edge_list, n) != -1 else -1))


# Optimized solution
def warshall(d, n):
    e = copy.deepcopy(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                # print(d[i][k], d[k][j], d[i][j])
                if i == k or k == j:
                    continue
                if d[i][k] + d[k][j] < d[i][j]:
                    return []
                if d[i][k] + d[k][j] == d[i][j]:
                    # print(d[i][k], d[k][j], d[i][j], i,j,k)
                    e[i][j] = 0
                    e[j][i] = 0
    return e
    
import copy
n = int(eval(input()))
edges = []

graph = [list(map(int, input().split())) for i in range(n)]
e = warshall(graph, n)
if e == []:
    print((-1))
    exit()
# print(e)
edge_list = [[] for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(n):
        if e[i][j] > 0:
            edge_list[i].append((e[i][j], j))
        if j > i and e[i][j]:
            ans += e[i][j]

print(ans)
# Original solution
n=int(eval(input()))
d=[]
ans=0
for i in range(n):
    tmp=[int(j) for j in input().split()]
    d.append(tmp)
for i in range(n):
    for j in range(i+1,n):
        ans+=d[i][j]

for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            if i==k or j==k:
                continue
            if d[i][j]>d[i][k]+d[k][j]:
                print((-1))
                exit()
            elif d[i][j]==d[i][k]+d[k][j]:
                ans-=d[i][j]
                break
print(ans)


# Optimized solution
n=int(eval(input()))
d=[]

for i in range(n):
    tmp=[int(j) for j in input().split()]
    d.append(tmp)

ans=[[0]*n for i in range(n)]

for i in range(n):
    for j in range(i+1,n):
        ans[i][j]=d[i][j]

for i in range(n):
    for j in range(i+1,n):
        for k in range(n):
            if i==k or j==k:
                continue
            if d[i][j]>d[i][k]+d[k][j]:
                print((-1))
                exit()
            elif d[i][j]==d[i][k]+d[k][j]:
                ans[i][j]=0
res=0
for i in range(n):
    res+=sum(ans[i])
print(res)
# Original solution
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()


# Optimized solution
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()
# Original solution
N = int(eval(input()))
A = [list(map(int, input().split())) for _ in range(N)]


def main():
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            for k in range(N):
                if i == k or j == k:
                    continue
                if A[i][j] > A[i][k] + A[k][j]:
                    print((-1))
                    return
    for i in range(N):
        for j in range(N):
            if i == j:
                continue
            for k in range(N):
                if i == k or j == k:
                    continue
                if A[i][k] >= A[i][j] + A[k][j]:
                    A[i][k] = float('INF')
    ans = 0
    for i in range(N):
        for j in range(N):
            if A[i][j] == float('INF'):
                continue
            ans += A[i][j]
            A[j][i] = 0
    print(ans)


main()


# Optimized solution
def main():
    N = int(eval(input()))
    A = [list(map(int, input().split())) for _ in range(N)]
    ans = 0
    for i in range(N):
        A[i][i] = float('INF')
    for i in range(N):
        for j in range(i):
            if i == j:
                A[i][j] = float('INF')
                continue
            b = min(list(map(sum, list(zip(A[i], A[j])))))
            if A[i][j] > b:
                print((-1))
                return
            if b > A[i][j]:
                ans += A[i][j]
    print(ans)


main()
# Original solution
n = int(eval(input()))
A = [list(map(int, input().split())) for _ in range(n)]
# 小さい順に調べていく
roads = []
for i in range(n-1):
    for j in range(i+1, n):
        roads.append((A[i][j], i, j))
roads = sorted(roads)

INF = 10**9*1
AD = [[INF]*n for _ in range(n)]
G = [[] for _ in range(n)]
edges = set()
from collections import deque
ok = True
ans = 0
for a, s, e in roads:
    # s to e
    q = deque([[s, 0]])
    visited = [INF] * n
    visited[s] = 0
    while q:
        node, dist = q.popleft()
        if node == e:
            # sからeにたどり着いて
            if dist == a:
                # あたえられた距離と同じならばOK
                break
            elif dist < a:
                # あたえられた距離より小さいならばaは最短距離じゃないNG
                ok = False
                break
        
        for nn, cost in G[node]:
            if dist+cost < visited[nn]:
                visited[nn] = dist+cost
                q.append([nn, dist+cost])
    else:
        # sからeにたどり着けなかったら最短距離確定
        AD[s][e] = a
        G[s].append((e, a))
        G[e].append((s, a))
        ans += a
    if not ok:
        break

print((ans if ok else -1))

# Optimized solution
n = int(eval(input()))
A = [list(map(int, input().split())) for _ in range(n)]
INF = 10**9 + 1
dp = [[INF]*n for _ in range(n)]

# コスト登録
for i, line in enumerate(A):
    for j, a in enumerate(line):
        dp[i][j] = a

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        d = dp[i][j]
        if d < A[i][j]:
            ans = -1
            break
        else:
            for k in range(n):
                if k == i or k == j:
                    continue
                if dp[i][k] + dp[k][j] == d:
                    break
            else:
                ans += d
    if ans == -1:
        break
print(ans)
# Original solution
N = int(eval(input()))
A = [list(map(int, input().split())) for _ in range(N)]

def sol():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = A[i][k] + A[k][j]
                if d < A[i][j]:
                    return - 1

    INF = 10**18

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if k == i or k == j:
                    continue

                if A[i][k] + A[k][j] == A[i][j]:
                    A[i][j] = INF

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

    return ans

print((sol()))


# Optimized solution
N = int(eval(input()))
A = [list(map(int, input().split())) for _ in range(N)]

def sol():
    for k in range(N):
        for i in range(N):
            for j in range(N):
                d = A[i][k] + A[k][j]
                if d < A[i][j]:
                    return - 1

    ret = 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][k] + A[k][j] == A[i][j]:
                    break
            else:
                ret += A[i][j]

    return ret

print((sol()))
# Original solution
N, *L = list(map(int, open(0).read().split()))
cost = []
for i, m in enumerate(zip(*[iter(L)]*N)):
  cost.append(m)
ans = 0
for i in range(N):
  for j in range(i):
    m = min(cost[i][k]+cost[k][j] if k!=i and k!=j else 10**10 for k in range(N))
    if m<cost[i][j]:
      print((-1))
      import sys
      sys.exit()
    if m!=cost[i][j]:
      ans += cost[i][j]
print(ans)

# Optimized solution
N, *L = list(map(int, open(0).read().split()))
cost = []
for m in zip(*[iter(L)]*N):
  cost.append(m)
ans = 0
for i in range(N):
  for j in range(i):
    for k in range(N):
      if k==i or k==j:
        continue
      if cost[i][j]>cost[i][k]+cost[k][j]:
        print((-1))
        import sys
        sys.exit()
      if cost[i][j]==cost[i][k]+cost[k][j]:
        break
    else:
      ans += cost[i][j]
print(ans)
# Original solution
import heapq
from collections import deque

N = int(eval(input()))
A = [[int(a) for a in input().split()] for _ in range(N)]

def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**9+1] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


Road = [[] for _ in range(N)]
h = []
for i in range(N):
    for j in range(i+1, N):
        heapq.heappush(h, (A[i][j], i, j))
        
m = h[0][0]
ans = 0
while h:
    t = heapq.heappop(h)
    cost = t[0]
    i = t[1]
    j = t[2]
    if cost < 2*m:
        Road[i].append((cost, j))
        Road[j].append((cost, i))
    else:
        d = dijkstra_heap(i, Road, N)
        if d[j] > cost:
            Road[i].append((cost, j))
            Road[j].append((cost, i))
        elif d[j] < cost:
            ans = -1
            break
            
if ans == 0:
    for i in range(N):
        for t in Road[i]:
            ans += t[0]
            
    ans //= 2
        
print(ans)

# Optimized solution
import heapq
from collections import deque

N = int(eval(input()))
A = [[int(a) for a in input().split()] for _ in range(N)]

def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**9+1] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


Road = [[] for _ in range(N)]
h = []
for i in range(N):
    for j in range(i+1, N):
        heapq.heappush(h, (A[i][j], i, j))
        
m = h[0][0]
D = [[10**9+1]*N for _ in range(N)]
ans = 0
while h:
    t = heapq.heappop(h)
    cost = t[0]
    i = t[1]
    j = t[2]
    if cost < 2*m:
        Road[i].append((cost, j))
        Road[j].append((cost, i))
        D[i][j] = cost
        D[j][i] = cost
    elif D[i][j] > cost:
        D[i] = dijkstra_heap(i, Road, N)
        if D[i][j] > cost:
            Road[i].append((cost, j))
            Road[j].append((cost, i))
            D[i][j] = cost
            D[j][i] = cost
    if D[i][j] < cost:
        ans = -1
        break
            
if ans == 0:
    for i in range(N):
        for t in Road[i]:
            ans += t[0]
            
    ans //= 2
        
print(ans)