CodeEff/ECCO huggingface dataset:
# Original solution
N = int(eval(input()))
src = [list(map(int,input().split())) for i in range(N)]

ans = 0
for k in range(N):
    for i in range(N):
        for j in range(N):
            if src[i][j] > src[i][k] + src[k][j]:
                print((-1))
                exit()

for i in range(N-1):
    for j in range(i+1,N):
        for k in range(N):
            if k==i or k==j: continue
            if src[i][j] == src[i][k] + src[k][j]:
                break
        else:
            ans += src[i][j]
print(ans)

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

for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j] > A[i][k] + A[k][j]:
                print((-1))
                exit()

ans = 0
for i in range(N-1):
    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]:
                break
        else:
            ans += A[i][j]
print(ans)
# Original solution
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
from heapq import*
N=int(eval(input()))
A=[list(map(int,input().split())) for i in range(N)]
data=[[] for i in range(N)]

for i in range(N):
    for m in range(N):
        if i==m:
            continue
        data[i].append([m,A[i][m],i*300+m])



visited={0}
stack=[]
dic={}
for p,c,i in data[0]:
    if c in dic:
        dic[c].append([p,i])
    else:
        dic[c]=[[p,i]]
    stack.append(c)
heapify(stack)
value=0
usedpath=set()
while stack:
    m=heappop(stack)
    a,i=dic[m].pop()
    if not a in visited:
        visited.add(a)
        usedpath.add(i)
        value+=m
        for p,c,i in data[a]:
            if not p in visited:
                if c in dic:
                    dic[c].append([p,i])
                else:
                    dic[c]=[[p,i]]
                heappush(stack,c)

idle_max=10**18
d=[[idle_max for i in range(N)] for m in range(N)]
for i in range(N):
    d[i][i]=0
for i in usedpath:
    i,m=i//300,i%300
    d[i][m]=A[i][m]
    d[m][i]=A[m][i]

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])
Alst=[[A[i][m],i,m] for i in range(N) for m in range(N)]
Alst=sorted(Alst,key=lambda x:x[0])
for B,i,m in Alst:
    if d[i][m]<A[i][m]:
        print((-1))
        exit()
    if d[i][m]>A[i][m]:
        d[i][m]=A[i][m]
        d[m][i]=A[m][i]
        value+=A[i][m]

        for i1 in range(N):
            for j in range(N):
                 d[i1][j] = min(d[i1][j], d[i1][i] + d[i][j])
                 d[i1][j] = min(d[i1][j], d[i1][m] + d[m][j])


print(value)


# Optimized solution
"""from collections import *
from itertools import *
from bisect import *
from heapq import *

import math
from fractions import gcd"""
from heapq import*
N=int(eval(input()))
A=[list(map(int,input().split())) for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j]>A[i][k]+A[k][j]:
                print((-1))
                exit()
res = 0
for i in range(N-1):
    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]:
                break
        else:
            res += A[i][j]
print(res)
# Original solution
n = int(eval(input()))
a = [list(map(int, input().split())) for i in range(n)]
b = [[1]*n for i in range(n)]

for i in range(n):
    for j in range(n):
        for k in range(n):
            if a[i][k] + a[k][j] < a[i][j]:
                print((-1))
                exit()
            elif a[i][k] + a[k][j] == a[i][j] and i!=k!=j:
                b[i][j] = 0

ans = 0
for i in range(n):
    for j in range(n):
        if b[i][j]:
            ans += a[i][j]
print((ans//2))

# Optimized solution
n = int(eval(input()))
a = [list(map(int, input().split())) for i in range(n)]
b = [[1]*n for i in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            if a[i][k] + a[k][j] < a[i][j]:
                print((-1))
                exit()
            elif a[i][k] + a[k][j] == a[i][j] and i!=k!=j:
                b[i][j] = 0

ans = 0
for i in range(n):
    for j in range(n):
        if b[i][j]:
            ans += a[i][j]
print((ans//2))
# Original solution
import copy
N = int(eval(input()))
A = [list(map(int, input().split())) for i in range(N)]
B = copy.deepcopy(A)
ans = 0
for i in range(N):
    ans += sum(A[i])
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if k == i or k == j:
                continue
            else:
                if B[i][k] == B[i][j]+B[j][k]:
                    ans -= B[i][k]
                B[i][k] = min(B[i][k], B[i][j]+B[j][k])

if A == B:
    print((ans//2))
else:
    print((-1))


# Optimized solution
import copy
N = int(eval(input()))
A = [list(map(int, input().split())) for i in range(N)]
B = copy.deepcopy(A)
table = [[True]*N for i in range(N)]
ans = 0
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if k == i or k == j:
                continue
            else:
                if B[i][k] == B[i][j]+B[j][k]:
                    table[i][k] = False
                B[i][k] = min(B[i][k], B[i][j]+B[j][k])


if A == B:
    for i in range(N):
        for j in range(N):
            if table[i][j]:
                ans += B[i][j]
    print((ans//2))
else:
    print((-1))
# Original solution
def main():
    N = int(eval(input()))
    A = []
    d = []
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(i+1, N):
            if Ai[j] > 0:
                d.append((Ai[j], i, j))
    d.sort(key=lambda x: x[0])


    def wf(dist):
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist


    ok = len(d)+1
    ng = 0
    mid = len(d)
    while ok - ng > 1:
        dist = [[10 ** 10 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            dist[i][i] = 0
        for x, i, j in d[:mid]:
            dist[i][j] = x
            dist[j][i] = x
        if wf(dist) == A:
            ok = mid
        else:
            ng = mid
            if ng == len(d):
                print((-1))
                exit()
        mid = (ok+ng)//2

    ans = 0
    for i in range(ok):
        ans += d[i][0]
    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
def main():
    N = int(eval(input()))
    A = []
    dist = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(N):
            dist[i][j] = Ai[j]

    def wf(dist):
        need = [[1 for _ in range(N)] for _ in range(N)]
        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]:
                        print((-1))
                        exit()
                    elif dist[i][j] == dist[i][k] + dist[k][j]:
                        if i != k and j != k:
                            need[i][j] = 0
                            need[j][i] = 0
        return need

    need = wf(dist)
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += need[i][j] * dist[i][j]
    print(ans)


if __name__ == '__main__':
    main()
# Original solution
N= int(eval(input()))

MP=[list(map(int,input().split())) for i in range(N)]
MP2=[]
for li in MP:
    MP2.append(li.copy())

MP3=[[-1]*N for _ in range(N)]

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            cand = MP2[i][k] + MP2[k][j]
            if cand <= MP2[i][j]:
                MP2[i][j] = cand
                if (i != k and j != k):
                    MP3[i][j] = k

for i in range(N):
    for j in range(N):
        if MP[i][j] != MP2[i][j]:
            print((-1))
            exit()

checked=set()

res = set()
def dfs(i,j):
    k = MP3[i][j]
    if k == -1:
        k = i
    if (i,j) in checked:
        return
    checked.add((i,j))
    if (i == k or j == k):
        if i < j:
            res.add((i,j))
    else:
        dfs(i,k)
        dfs(k,j)

for i in range(N):
    for j in range(N):
        dfs(i,j)

ressum = 0
for i,j in res:
    ressum += MP[i][j]

# for li in MP3:
#     print(li)
# print(res)
print(ressum)


# Optimized solution
N=int(eval(input()))
MP=[list(map(int,input().split())) for i in range(N)]
MP2=[]
for li in MP:
    MP2.append([i for i in li])

MP3=[[-1]*N for _ in range(N)]

# ワーシャルフロイド
for k in range(N):
    for i in range(N):
        for j in range(N):
            cand = MP2[i][k] + MP2[k][j]
            if cand <= MP2[i][j]:
                MP2[i][j] = cand
                if (i != k and j != k):
                    MP3[i][j] = k

for i in range(N):
    for j in range(N):
        if MP[i][j] != MP2[i][j]:
            print((-1))
            exit()

checked=set()

res = set()
def dfs(i,j):
    k = MP3[i][j]
    if k == -1:
        k = i
    if (i,j) in checked:
        return
    checked.add((i,j))
    if (i == k or j == k):
        if i < j:
            res.add((i,j))
    else:
        dfs(i,k)
        dfs(k,j)

for i in range(N):
    for j in range(N):
        dfs(i,j)

ressum = 0
for i,j in res:
    ressum += MP[i][j]

# for li in MP3:
#     print(li)
# print(res)
print(ressum)
# Original solution
from heapq import heappush,heappop,heapify
INF=10**18

def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            siz[a]+=siz[b]
        else:
            par[a]=b
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
def size(a):
    return siz[find(a)]
def same(a,b):
    return find(a)==find(b)

def dijkstra(G,s,g,n):
    que=[(0,s)]
    dist=[INF]*n
    dist[s]=0
    while que:
        mincost,u=heappop(que)
        if(mincost>dist[u]):
            continue
        if(u==g):
            return dist
        if(G[u]):
            for c,v in G[u]:
                if(dist[u]+c<dist[v]):
                    dist[v]=dist[u]+c
                    heappush(que,(dist[v],v))
    return dist

N=int(eval(input()))
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]

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

G=[set() for i in range(N)]
Edges=[]
for i in range(N):
    for j in range(N):
        if(i==j):
            continue
        Edges.append([A[i][j],i,j])
Edges.sort(key=lambda x:x[0])

res=0
for i in range(len(Edges)):
    cost,fr,to=Edges[i]
    if not same(fr,to):
        union(fr,to)
        G[fr].add((cost,to))
        G[to].add((cost,fr))
        res+=cost
    else:
        di=dijkstra(G,fr,to,N)
        if di[to]<A[fr][to]:
            print((-1))
            exit()
        if di[to]>cost:
            G[fr].add((cost,to))
            G[to].add((cost,fr))
            res+=cost
print(res)

# Optimized solution
N=int(eval(input()))
A=[list(map(int,input().split())) for i in range(N)]
res=0
flag=[[False]*N for i in range(N)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            if A[i][j]>A[i][k]+A[k][j]:
                print((-1))
                exit()
            elif k!=i and k!=j and A[i][j]==A[i][k]+A[k][j] and not flag[i][j] and not flag[j][i]:
                flag[i][j]=True
                flag[j][i]=True
                res-=A[i][j]
ans=sum(sum(A[i]) for i in range(N))//2+res

print(ans)
# Original solution
import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def main():
    n = int(eval(input()))
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    for i in range(n-1):
        que = []
        d = [10**15 for _ in range(n)]
        d[i] = 0
        heappush( que,(0,i) )
        while que:
            p =  heappop(que)
            v = p[1]
            if d[v] < p[0]:
                continue
            for k in range(len(g[v])):
                edge = g[v][k]
                if d[edge[0]] > d[v] + edge[1]:
                    d[edge[0]] = d[v] + edge[1]
                    heappush( que,(d[edge[0]] , edge[0]) )
        if d != a[i]:
            print((-1))
            return
        for j in range(i+1,n):
            que = []
            d = [10**15 for _ in range(n)]
            d[i] = 0
            heappush( que,(0,i) )
            while que:
                p =  heappop(que)
                v = p[1]
                if d[v] < p[0]:
                    continue
                for k in range(len(g[v])):
                    edge = g[v][k]
                    if (edge[0], v) == (i,j) or (edge[0], v) == (j,i):
                        continue
                    if d[edge[0]] > d[v] + edge[1]:
                        d[edge[0]] = d[v] + edge[1]
                        heappush( que,(d[edge[0]] , edge[0]) )
            if d[j] == a[i][j]:
                ans -= a[i][j]
    print(ans)

if __name__ == "__main__":
    main()

# Optimized solution
import sys
from heapq import heappop, heappush
input = sys.stdin.readline

def main():
    n = int(eval(input()))
    a = [list(map(int,input().split())) for _ in range(n)]
    g = [[] for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1,n):
            g[i].append((j,a[i][j]))
            g[j].append((i,a[i][j]))
    ans = 0
    for i in range(n):
        ans += sum(a[i])
    ans //= 2
    w = []
    for i in range(n):
        que = []
        d = [10**15 for _ in range(n)]
        d[i] = 0
        heappush( que,(0,i) )
        while que:
            p =  heappop(que)
            v = p[1]
            if d[v] < p[0]:
                continue
            for k in range(len(g[v])):
                edge = g[v][k]
                if d[edge[0]] > d[v] + edge[1]:
                    d[edge[0]] = d[v] + edge[1]
                    heappush( que,(d[edge[0]] , edge[0]) )
        w.append(d)
    for i in range(n-1):
        for j in range(i+1,n):
            if w[i][j] < a[i][j]:
                print((-1))
                return
            flag = 0
            for k in range(n):
                if i == k or j == k:
                    continue
                if w[i][k] + w[k][j] == w[i][j]:
                    flag = 1
            if flag:
                ans -= w[i][j]
    print(ans)

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

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N = int(readline())
    G = [list(map(int, readline().split())) for _ in range(N)]

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            needed = True
            for k in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    print((-1))
                    return
                if k not in (i, j) and G[i][j] == G[i][k] + G[k][j]:
                    needed = False
            if needed:
                ans += G[i][j]

    print(ans)
    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N = int(readline())
    G = [list(map(int, readline().split())) for _ in range(N)]

    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            needed = True
            for k in range(N):
                if k == i or k == j:
                    continue
                if G[i][j] > G[i][k] + G[k][j]:
                    print((-1))
                    return
                if G[i][j] == G[i][k] + G[k][j]:
                    needed = False
            if needed:
                ans += G[i][j]

    print(ans)
    return


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

N = int(eval(input()))
A = []
for i in range(N):
    A.append(list(map(int, input().split())))

B = copy.deepcopy(A)
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        for k in range(N):
            if j == k:
                continue
            if k == i:
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print((-1))
                exit()
            if A[i][j] == A[i][k] + A[k][j]:
                B[i][j] = 0

ans = 0
for i in range(N):
    for j in range(i, N):
        ans += B[i][j]

print(ans)



# Optimized solution
import copy

N = int(eval(input()))
A = []
for i in range(N):
    A.append(list(map(int, input().split())))

B = copy.deepcopy(A)
for i in range(N):
    for j in range(i, N):
        for k in range(N):
            if not (i != j and j != k and k != i):
                continue
            if A[i][j] > A[i][k] + A[k][j]:
                print((-1))
                exit()
            if A[i][j] == A[i][k] + A[k][j]:
                B[i][j] = 0

ans = 0
for i in range(N):
    for j in range(i, N):
        ans += B[i][j]

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

nA = [line[:] for line in A]
cnt = 0

for k in range(N):
    for i in range(N):
        for j in range(N):
            if nA[i][j] > nA[i][k] + nA[k][j]:
                nA[i][j] = nA[i][k] + nA[k][j]
            elif not(i == j or j == k or k == i) and nA[i][j] == nA[i][k] + nA[k][j]:
                cnt += nA[i][j]

if A != nA:
    print((-1))
else:
    ans = sum(sum(line) for line in A) - cnt
    ans //= 2
    print(ans)

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

flag = [[0] * N for _ in range(N)]
dist = [line[:] for line in A]

for k in range(N):
    for i in range(N):
        for j in range(N):
            if i == j or j == k or k == i:
                continue
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
            elif dist[i][j] < dist[i][k] + dist[k][j]:
                flag[i][j] += 1

if A != dist:
    print((-1))
    exit()

ans = 0
for i in range(N):
    for j in range(N):
        if flag[i][j] == N-2:
            ans += A[i][j]

ans //= 2
print(ans)
# Original solution
N = int(eval(input()))
A = [list(map(int,input().split())) for _ in range(N)]

flag = [[0] * N for _ in range(N)]
dist = [line[:] for line in A]

for k in range(N):
    for i in range(N):
        for j in range(N):
            if i == j or j == k or k == i:
                continue
            if dist[i][j] > dist[i][k] + dist[k][j]:
                dist[i][j] = dist[i][k] + dist[k][j]
            elif dist[i][j] < dist[i][k] + dist[k][j]:
                flag[i][j] += 1

if A != dist:
    print((-1))
    exit()

ans = 0
for i in range(N):
    for j in range(N):
        if flag[i][j] == N-2:
            ans += A[i][j]

ans //= 2
print(ans)

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

flag = [[True] * N for _ in range(N)]

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]:
                print((-1))
                exit()
            elif A[i][j] == A[i][k] + A[k][j]:
                flag[i][j] = False

ans = 0

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

print(ans)
# Original solution
def dfs(s, stack):
    visited[s] = 1
    if s in stack:
        print((1))
        exit()
    else:
        stack.append(s)
        for t in adj[s]:
            dfs(t, stack)
        stack.remove(s)

nv, ne = list(map(int, input().split(' ')))
adj = [[] for _ in range(nv)]
visited = [0] * nv

for _ in range(ne):
    s, t = list(map(int, input().split(' ')))
    adj[s].append(t)

while sum(visited) < nv:
    r = 0
    while visited[r]: r += 1
    dfs(r, [])

print((0))

# Optimized solution
def dfs(s):
    if not visited[s]:
        visited[s] = True
        stack[s] = True
        for t in adj[s]:
            if stack[t]:
                print((1))
                exit()
            else:
                dfs(t)
    stack[s] = False

nv, ne = list(map(int, input().split(' ')))
adj = [[] for _ in range(nv)]
visited = [False] * nv
stack = [False] * nv

for _ in range(ne):
    s, t = list(map(int, input().split(' ')))
    adj[s].append(t)

for i in range(nv):
    dfs(i)

print((0))
# Original solution
from collections import UserList
class Stack(UserList):
    def __init__(self, *args):
        UserList.__init__(self, *args)
        self.contains = set()
    def __contains__(self, x):
        return x in self.contains
    def __and__(self, x):
        return self.contains & x
    def push(self, x):
        if x in self.contains:
            return
        self.data.append(x)
        self.contains |= {x}
    def pop(self):
        x = self.data.pop()
        self.contains -= {x}
        return x

def is_contain_cycle(g, v):
    visited = set()
    for i in range(v):
        if i in visited:
            continue
        route = Stack([None])
        dfs_stack = [(i, None)]            
        while dfs_stack:
            u, prev = dfs_stack.pop()
            while route[-1] != prev:
                route.pop()
                
            visited |= {u}
            if u in route:
                return True
            dfs_stack.extend((v, u) for v in g[u])
            
            route.push(u)
    return False

from sys import stdin
from collections import defaultdict
readline = stdin.readline

v, e = list(map(int, readline().split()))
g = defaultdict(set)
for i in range(e):
    s, t = list(map(int, readline().split()))
    g[s] |= {t}
print((1 if is_contain_cycle(g, v) else 0))

# Optimized solution
def is_contain_cycle(g, v):
    visited = set()
    for i in range(v):
        if i in visited:
            continue
        #route = Stack([None])
        route = [None]
        dfs_stack = [(i, None)]
        while dfs_stack:
            u, prev = dfs_stack.pop()
            while route[-1] != prev:
                route.pop()
            if u in route:
                return True
            if u in visited:
                continue
            visited |= {u}
            dfs_stack.extend((v, u) for v in g[u])
            route.append(u)
    return False

from sys import stdin
from collections import defaultdict


readline = stdin.readline

v, e = list(map(int, readline().split()))
g = defaultdict(set)
for i in range(e):
    s, t = list(map(int, readline().split()))
    g[s] |= {t}
print((1 if is_contain_cycle(g, v) else 0))
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))
x = 2020202020
for i in range(1, n):
    x = min(x, abs(sum(a[:i]) - sum(a[i:])))
print(x)


# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))
x = 0
y = sum(a)
ans = 2020202020
for i in range(n - 1):
    x += a[i]
    y -= a[i]
    ans = min(ans, abs(x - y))
print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split())) # 横入力

b = [0]
aaa = 0
for i in range(n):
    aaa += a[i]
    b.append(aaa)

ans = 202020202020
for i in range(n):
    ans = min(ans, abs(sum(a) - b[i]*2))
print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split())) # 横入力

x = [0]
aaa = 0
for i in range(n):
    aaa += a[i]
    x.append(aaa)
aa = sum(a)
y = [aa]
for i in range(n):
    aa -= a[i]
    y.append(aa)

ans = 202020202020
for i in range(n+1):
    ans = min(ans, abs(x[i] - y[i]))

print(ans)