CodeEff/ECCO huggingface dataset:
# Original solution
N,K =  list(map(int,input().split()))
if K == 1 or N%K == 0:
    print((0))
    exit()
S = set()
S.add(N)
for x in range(N):
    c = abs(N-K)
    if N == c:
        break
    N = abs(N-K)
    S.add(N)
print((min(S)))

# Optimized solution
N,K =  list(map(int,input().split()))
T = N%K
L = [T,abs(T-K)]
print((min(L)))
# Original solution
import sys
N, K = list(map(int, input().split()))
first = N
list_a = []

if N % K == 0:
    print((0))
    sys.exit()
else:
    while N > 0:
        N = N - K

second = N + K

N = abs(N)

list_a.append(N)
list_a.append(second)
list_a.append(first)

list_a = sorted(list_a)

print((list_a[0]))


# Optimized solution
import sys
N, K = list(map(int, input().split()))
first = N
list_a = []

if N % K == 0:
    print((0))
    sys.exit()
else:
    X = N // K
    N = N - (K * (X+1))

second = N + K

N = abs(N)

list_a.append(N)
list_a.append(second)
list_a.append(first)

list_a = sorted(list_a)

print((list_a[0]))
# Original solution
N,K=list(map(int,input().split()))

if N % K ==0:
  print((0))
  exit()
  
ans = N
for i in range((N//K)+1):
  N = abs(N-K)
  ans =min(ans,N)
  
  
print(ans)

# Optimized solution
N,K=list(map(int,input().split()))

if N % K ==0:
  print((0))
  exit()
  
if N < K:
  print((min(N,K-N)))
  exit()

if N > K:
  print((min(N%K,K-(N%K))))
# Original solution
n, k = list(map(int,input().split()))

if k == 1:
    print((0))
    exit()
while n >= abs(n-k):
    n = abs(n-k)
    
print(n)

# Optimized solution
n, k = list(map(int,input().split()))
print((min(n%k, k - n%k)))
# Original solution
N, K = [int(n) for n in input().split()]

def cmp(a, b):
    if a > b:
        return a%b
    return abs(a-b)

while True:
    ans = cmp(N, K)
    if 0 <= ans <=2:
        break
    N = ans
print(ans)         


# Optimized solution
N, K = [int(n) for n in input().split()]
print((min(N%K, K-(N%K))))
# Original solution
n, k = list(map(int, input().split()))

t = n // k
re = n - t * k

i = True

while i == True:
    if abs(re - k) < re:
        re = abs(re - k)
        i = True
    else:
        i = False

print(re)


# Optimized solution
n, k = list(map(int, input().split()))

t = n // k
re = n - t * k


if abs(re - k) < re:
    re = abs(re - k)
    i = True

print(re)
# Original solution
N,K = list(map(int, input().split()))
if N % K == 0:
    print((0))
elif N > K:
    while N > 0:
        hako1 = N
        N -= K
        hako2 = abs(N)
    if hako1 > hako2:
      print(hako2)
    else:
      print(hako1)
else:
    if N >= abs(N-K):
        print((abs(N-K)))
    else:
        print(N)

# Optimized solution
N,K = list(map(int, input().split()))
if N % K == 0:
    print((0))
elif N > K:
    hako1 = N%K
    hako2 = abs(hako1-K)
    if hako1 > hako2:
      print(hako2)
    else:
      print(hako1)
else:
    if N >= abs(N-K):
        print((abs(N-K)))
    else:
        print(N)
# Original solution
N, K = [int(x) for x in input().split(" ")]

if N ==0 or K==1:
  print((0))
else:
  while N>abs(N-K):
    N = abs(N%K-K)
  print(N)


# Optimized solution
N, K = [int(x) for x in input().split(" ")]

if N ==0 or K==1 or N == K:
  print((0))
else:
  while N>abs(N-K):
    N = abs(N%K-K)
  print(N)
# Original solution
a,b = list(map(int, input().split()))

if b == 1:
    print((0))
    exit()
      
while True:
    x = abs(a-b)
    if x < a:
        a = x
    else:
        print(a)
        break

# Optimized solution
a,b = list(map(int, input().split()))

if a > b:
    if a % b == 0:
        print((0))
        exit()
    else:
        print((min(a%b, b-(a%b))))
        exit()

while True:
    x = abs(a-b)
    if x < a:
        a = x
    else:
        print(a)
        break
# Original solution
n,k = list(map(int,input().split()))
N = n
if n % k == 0:
    print((0))
else:
    while n > 0:
        n -= k
    if abs(n) > N:
        print(N)
    else:
        print((abs(n)))


# Optimized solution
n,k = list(map(int,input().split()))
a = n % k
print((min(abs(a-k),a)))
# Original solution
n, k = list(map(int, input().split()))
if n==k or k==1:
  print((0))
else:
  ans=n
  res=[ans]
  while(1):
    ans=abs(ans-k)
    if ans in res or ans == k:
      break
    res.append(ans)
  print((min(res)))

# Optimized solution
n, k = list(map(int, input().split()))
print((min(n%k, k - n%k)))
# Original solution
N , K = input().split()
N = int(N)
K = int(K)

print((min(N % K , K - N % K)))

# Optimized solution
n, k = list(map(int,input().split()))
m = n %k
print((min(m, abs(m-k))))
# Original solution
#
N, K = list(map(int,input().split()))
N  %= K
min = N
for i in range(10**6):
    N = abs(N-K)
    if min > N:
        min = N
    if N == 0:
        min = 0
        break
print(min)

# Optimized solution
#input
N, K = list(map(int,input().split()))

#main
t = N % K
ans = min(t, K - t)

#output
print(ans)
# Original solution
n,k = list(map(int,input().split()))
if n%k==0:
    print((0))
else:
    while(n > abs(n-k)):
        if k == 1:
            n=0
            break
        n=abs(n-k)
    print(n)

# Optimized solution
n,k = list(map(int,input().split()))
ans = min(n%k,k-(n%k))
print(ans)
# Original solution
import sys
N, K = list(map(int, input().split()))

if K == 1:
    print((0))
    sys.exit()

current = N

while True:
    prev = current
    current = abs(current - K)
    next = abs(current - K)
    if prev == next:
        print((min(current, next)))
        break


# Optimized solution
import sys
N, K = list(map(int, input().split()))

if K == 1:
    print((0))
    sys.exit()

a = abs(N - K * (N // K + 1))
print((min(a, abs(a - K))))
# Original solution
N, K = list(map(int, input().split()))
Nj = N
while True:
    Ni = Nj
    Nj = abs(Ni - K)
    if Ni > N:
        print(N)
        break
    elif Nj > Ni:
        print(Ni)
        break
    elif K == 1 or Nj == K:
        print((0))
        break
    else:
        continue

# Optimized solution
N, K  = list(map(int, input().split()))
a = N % K
print((min(abs(a - K), a)))
# Original solution
N,K=list(map(int,input().split()))

for i in range(18):
    if N > 10 ** i * K:
        for j in range(999):
            if N > j*10 ** i * K:
                N=N-j*10 ** i * K


while abs(N-K)<N:
    N=abs(N-K)

print(N)

# Optimized solution
N,K=list(map(int,input().split()))



for i in reversed(list(range(18))):
    while N > 10 ** i * K:
        N=N-10 ** i * K


while abs(N-K)<N:

    N=abs(N-K)

print(N)
# Original solution
n, k = list(map(int, input().split()))


if k == 1:
    n = 0
else:
    while True:
        if abs(k - n) < n:
            n = abs(k - n)
        else:
            FLG = True
            break

print(n)

# Optimized solution
n, k = list(map(int, input().split()))

if n >= k:
    n -= k * (n // k)      

if k-n > n:
    print(n)
else:
    print((k-n))
# Original solution
N, K = list(map(int, input().split()))
if N % K == 0:
    print((0))
else:
    li = []
    li.append(N)
    aoki = N
    while aoki <= min(li):
        aoki = abs(min(li) - K)
        li.append(aoki)
    print((min(li)))


# Optimized solution
n, k = list(map(int, input().split()))
if n==0 or k==1:
    print((0))
    exit()
elif n<k:
    print((min(n, abs(n-k))))
    exit()
elif n % k == 0:
    print((0))
    exit()
else:
    mx = n%k
print((min(abs(mx-k), mx)))
# Original solution
N,K = list(map(int,input().split()))
if(K==1 and N>1):
    print((int(0)))
elif(N==0 and K>=1):
    print((int(0)))
else:
    i = 0
    l = 100000000000000000
    r = []
    while(i==0):
        r.append(N)
        s = abs(N-K)
        if(l>s):
            l = s
        N = s
        if(N in r):
            i+=1
    print(l)

# Optimized solution
N,K = list(map(int,input().split()))
if(N==0):
    print((int(0)))
else:
    r = N%K
    print((min(r,K-r)))
# Original solution
n,k = list(map(int, input().split()))
mi = n
loop = True

if n%k==0:
  mi = 0
  loop = False

while loop:
  loop = False
  if mi > abs(n-k):
    loop = True
    n = abs(n-k)
    mi = n

print(mi)

# Optimized solution
n,k = list(map(int, input().split()))
mi = n%k
if mi > abs(mi-k):
  print((abs(mi-k)))
else:
  print(mi)
# Original solution
X = list(map(int, input().split()))
N = X[0]
K = X[1]
if N % K == 0:
  print((0))
else:
  while True:
    A = abs(N - K)
    if N > A:
      N = A
    else:
      break
  print(N)

# Optimized solution
X = list(map(int, input().split()))
N = X[0]
K = X[1]
t = N % K
s = K - t
if t <= s:
  print(t)
else:
  print(s)
# Original solution
import sys


def input():
    return sys.stdin.readline().strip()

def main():
    n, k = list(map(int, input().split()))
    if k == 1:
        n = 0
        print(n)
        return
    while n > k//2:
        n = abs(n-k)
    print(n)

main()

# Optimized solution
import sys


def input():
    return sys.stdin.readline().strip()

def main():
    n, k = list(map(int, input().split()))
    a = n % k
    print((min(a, k-a)))

main()
# Original solution
n,k=list(map(int,input().split()))
if n==0 or k==0:
    print((0))
    exit()

if n%k==0:
    print((0))
    exit()
    
while n > abs(n-k):
    n=abs(n-k)
print(n)

# Optimized solution
n,k=list(map(int,input().split()))
amari=n%k
if n==0:
    print((0))
    exit()

elif n%k==0:
    print((0))
    exit()


else:
    print((min(amari,k-amari)))

'''    
while n > abs(n-k):
    n=abs(n-k)
print(n)
'''
# Original solution
def main():
        N, K = list(map(int, input().split()))
        # K: fixed

        ans = 0

        if N%K==0:
                ans = 0
        else:
                if N>=K:
                        temp = K
                        while temp<N:
                                temp += K
                        upper = temp-N
                        lower = abs(upper-K)
                        ans = min(upper, lower)
                else:
                        ans = min(N, K-N)

        print(("{}".format(ans)))

if __name__=="__main__":
        main()

# Optimized solution
def main():
        N, K = list(map(int, input().split()))
        # K: fixed
        ans = 0
        r = N%K

        if N%K==0:
                ans = 0
        else:
                ans = min(r, abs(r-K))

        print(("{}".format(ans)))

if __name__=="__main__":
        main()
# Original solution
n, k = list(map(int, input().split()))
if n % k == 0:
	print((0))
else:
	while True:
		prev = n
		n = abs(n - k)
		if n >= prev:
			break
	print(prev)


# Optimized solution
n, k = list(map(int, input().split()))
p = n // k
print((min(abs(n - p * k), abs(n - (p + 1) * k))))
# Original solution
import sys
n,k=list(map(int,input().split()))
if n%k==0:
    print((0))
    sys.exit()
while abs(n-k)<n:
    n=abs(n-k)
    
    if n==0:
        print(n)
        sys.exit()
else:
    print(n)

# Optimized solution
import sys
n,k=list(map(int,input().split()))
if n%k==0:
    print((0))
    sys.exit()
if n%k<abs(k-n%k):
    print((n%k))
else:
    print((abs(k-n%k)))
# Original solution
#coding: utf-8
A = list(map(int, input().split()))
N = A[0]
K = A[1]

n = 0
sw = 0
while True:
  if N%K == 0:
    N = 0
    break
  sw = abs(N-K)
  n += 1
  if N > sw:
    N = sw
  else:
    break
print(N)

# Optimized solution
#coding: utf-8
A = list(map(int, input().split()))
N = A[0]
K = A[1]

n = 0
sw = 0
while True:
  if N%K == 0:
    N = 0
    break
  if (N/K) //1:
    C = N//K
    N = N-C*K

  sw = abs(N-K)
  n += 1
  if N > sw:
    N = sw
  else:
    break
print(N)
# Original solution
n,k = list(map(int,input().split()))

if k == 1:
    print((0))
else:
    for i in range(1000000000000000000):
        if n > abs(n-k):
            n = abs(n-k)
        elif n <= abs(n-k):
            break
    print(n)

# Optimized solution
n,k = list(map(int,input().split()))

# if k == 1:
#     print(0)
# else:
#     for i in range(1000000000000000000):
#         if n > abs(n-k):
#             n = abs(n-k)
#         elif n <= abs(n-k):
#             break
#     print(n)
amari = n % k
if abs(amari-k) < amari:
    print((abs(amari-k)))
else:
    print(amari)
# Original solution
n,k = list(map(int,input().split()))
if(k==1):
  print((0))
else:
  t = n//k
  for i in range(t):
    n = abs(n-k)
  if(n < abs(k-n)):
    print(n)
  else:
    print((abs(k-n)))

# Optimized solution
N, K = list(map(int,input().split()))
t = N%K
if (K - t) >= t:
    print(t)
else:
    print((K - t))
# Original solution
n, k = list(map(int, input().split()))

if n % k == 0:
  print((0))
else: 
  ans = n
  while ans > abs(n-k):
    n = abs(n - k)
    ans = min(n, ans)
  print(ans)

# Optimized solution
n, k = list(map(int, input().split()))

if n % k == 0:
  print((0))
else: 
  ans = n % k
  #print(ans)
  while ans > k//2:
    n = abs(ans - k)
    ans = min(n, ans)
  print(ans)
# Original solution
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(eval(input()))
A=[]
# ans=0
for i in range(n):
    a=list(map(int,input().split()))
    A.append(a)
    # ans+=sum(a)

#ans//=2
miti=A[:]
for k in range(n):
    for i in range(k):
        for j in range(i):
            q=miti[i][j]
            w=miti[j][k]
            e=miti[k][i]
            q,w,e=sorted([[q,i,j],[w,j,k],[e,k,i]])
            if e[0]==inf:
                continue
            if sum([q[0],w[0],e[0]])==e[0]*2:
                miti[e[1]][e[2]]=inf
                miti[e[2]][e[1]]=inf
            elif q[0]+w[0]<e[0]:
                print((-1));exit()
ans=0
for i in range(n):
    for j in range(n):
        if miti[i][j]!=inf:
            ans+=miti[i][j]

print((ans//2))


# Optimized solution
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict, OrderedDict
#すべてのkeyが用意されてる defaultdict(int)で初期化
#順序を保ったdict
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(eval(input()))
A=[]
# ans=0
for i in range(n):
    a=list(map(int,input().split()))
    A.append(a)
    # ans+=sum(a)

#ans//=2
miti=[[] for i in range(n)]
for i in range(n):
    miti[i]=A[i][:]
    
for k in range(n):
    for j in range(k):
        for i in range(j):
            q=A[i][j]
            w=A[j][k]
            e=A[k][i]
            #print(i,j,k,"\t",q,w,e)
            # q,w,e=sorted([[q,i,j],[w,j,k],[e,k,i]])
            # if max(q,w,e)==inf: continue
            if q+w==e and q!=inf and w!=inf: miti[k][i]=inf;miti[i][k]=inf;continue
            if q+w<A[k][i] and q!=inf and w!=inf: print((-1));exit()
            if w+e==q and e!=inf and w!=inf: miti[i][j]=inf;miti[j][i]=inf;continue
            if w+e<A[i][j]  and e!=inf and w!=inf : print((-1));exit()
            if e+q==A[j][k] and q!=inf and e!=inf: miti[j][k]=inf;miti[k][j]=inf;continue
            if e+q<A[j][k] and q!=inf and e!=inf: print((-1));exit()
            
            
                
            
ans=0
for i in range(n):
    for j in range(n):
        if miti[i][j]!=inf:
            ans+=miti[i][j]

print((ans//2))
# Original solution
import copy
ans=0
n=int(eval(input()))
l=[list(map(int,input().split())) for _ in [0]*n]
o=copy.deepcopy(l)

for k in range(n):
  for i in range(n):
    for j in range(n):
      if l[i][j]>l[i][k]+l[k][j]:
        print((-1))
        exit()
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 o[i][j]==o[i][k]+o[k][j]:
            o[i][j]=float("inf")
for i in range(n):
    for j in range(n):
        if o[i][j] != float("inf") :
            ans+=o[i][j]
print((ans//2))


# Optimized solution
INF = 10 ** 12

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

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

res = 0
for i in range(N):
    for j in range(i + 1, N):
        for k in range(N):
            if i != k and j != k and a[i][j] == a[i][k] + a[k][j]:
                break
        else:
            res += a[i][j]

print(res)
# Original solution
from itertools import product

N = int(eval(input()))
r = list(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))

# Optimized solution
from itertools import product

N = int(eval(input()))
r = list(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))
# Original solution
import sys
from copy import deepcopy as dc
input = sys.stdin.buffer.readline
N = int(eval(input()))
d = [list(map(int, input().split())) for _ in range(N)]
d2 = dc(d)
for k in range(N):
  for i in range(N):
    for j in range(N):
      d2[i][j] = min(d2[i][k] + d2[k][j], d2[i][j])
f = 0
for i in range(N):
  for j in range(N):
    if d[i][j] != d2[i][j]:
      f = 1
if f:
  print((-1))
else:
  res = 0
  for i in range(N):
    for j in range(N):
      x = 1
      for k in range(N):
        if k != i and k != j:
          if d[i][j] == d[i][k] + d[k][j]: x = 0
      res += x * d[i][j]
          
  print((res // 2))

# Optimized solution
N = int(eval(input()))
a = [list(map(int, input().split())) for _ in range(N)]
b = [a[i][: ] for i in range(N)]
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])
inf = 10 ** 10
if a == b:
 dp = [[inf] * N for _ in range(N)]
 for i in range(N):
  for j in range(N):
   mn = i
   for k in range(N):
    if k == j: continue
    if a[i][k] + a[k][j] == a[i][j]:
     if a[mn][j] > a[k][j]:
      mn = k
   if dp[mn][j] == inf:
    dp[mn][j] = a[mn][j]
   elif dp[mn][j] != a[mn][j]:
    print((-1))
    exit(0)
 for i in range(N):
  for j in range(N):
   if dp[i][j] == inf: dp[i][j] = 0
 print((sum([sum(dp[i]) for i in range(N)]) // 2))
else: print((-1))
# Original solution
from collections import deque
import sys
input = sys.stdin.readline


N = int(eval(input()))
A = [list(map(int, input().split())) for _ in range(N)]
dist = [[float('inf')] * N for _ in range(N)]
for i in range(N):
    dist[i][i] = 0
edges = []
for i in range(N-1):
    for j in range(i+1, N):
        edges.append((A[i][j], i, j))
edges.sort()
edges = deque(edges)
ans = 0
while edges:
    d, u, v = edges.popleft()
    if d > dist[u][v]:
        ans = -1
        break
    if d < dist[u][v]:
        ans += d
        for i in range(N-1):
            for j in range(i+1, N):
                ndist = min(dist[i][j], dist[i][u] + d + dist[v][j], dist[i][v] + d + dist[u][j])
                dist[i][j] = dist[j][i] = ndist
print(ans)


# Optimized solution
from copy import deepcopy
import sys
input = sys.stdin.readline


def floyd_warshall(dist):
    v = len(dist)
    for k in range(v):
        for i in range(v):
            for j in range(v):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])


N = int(eval(input()))
A = [list(map(int, input().split())) for _ in range(N)]
dist = deepcopy(A)
floyd_warshall(dist)
edges = []
for u in range(N-1):
    for v in range(u+1, N):
        edges.append((A[u][v], u, v))
edges.sort()
ans = 0
for d, u, v in edges:
    if dist[u][v] < d:
        ans = -1
        break
    ok = False
    for w in range(N):
        if w == u or w == v:
            continue
        if dist[u][w] + dist[w][v] == dist[u][v]:
            ok = True
            break
    if not ok:
        ans += d
print(ans)
# Original solution
from heapq import heappush, heappop

INF = 10 ** 20
n = int(eval(input()))
que = []
for i in range(n):
    aList = list(map(int, input().split()))
    for j in range(i, n):
        heappush(que, (aList[j], i, j))

dist = [[INF] * n for _ in range(n)]
ans = 0
while que:
    c, i, j = heappop(que)
    minDist = INF
    for k in range(n):
        minDist = min(minDist, dist[i][k] + dist[k][j])
    if minDist < c:
        print((-1))
        break
    elif minDist == c:
        continue
    else:
        dist[i][j] = dist[j][i] = c
        ans += c
else:
    print(ans)



# Optimized solution
INF = 10 ** 20
n = int(eval(input()))
edges = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * n for _ in range(n)]

edgeList = []
for i in range(n):
    for j in range(i, n):
        edgeList.append((edges[i][j], i, j))
edgeList.sort()

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], edges[i][k] + edges[k][j])
ans = 0
for c, i, j in edgeList:
    minCost = min([dist[i][k] + dist[k][j] for k in range(n) if (k != i and k != j)] + [INF])
    if c > minCost:
        print((-1))
        break
    if c < minCost:
        ans += c
else:
    print(ans)
# Original solution
INF = 10 ** 20
n = int(eval(input()))
edges = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * n for _ in range(n)]

edgeList = []
for i in range(n):
    for j in range(i, n):
        edgeList.append((edges[i][j], i, j))
edgeList.sort()

for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], edges[i][k] + edges[k][j])
ans = 0
for c, i, j in edgeList:
    minCost = min([dist[i][k] + dist[k][j] for k in range(n) if (k != i and k != j)] + [INF])
    if c > minCost:
        print((-1))
        break
    if c < minCost:
        ans += c
else:
    print(ans)

# Optimized solution
INF = 10 ** 20
n = int(eval(input()))
edges = [list(map(int, input().split())) for _ in range(n)]
dist = [[INF] * n for _ in range(n)]

edgeList = []
for i in range(n):
    for j in range(i, n):
        edgeList.append((edges[i][j], i, j))
edgeList.sort()

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

ans = 0
for c, i, j in edgeList:
    minCost = INF
    for k in range(n):
        if k in (i, j):continue
        if minCost > dist[i][k] + dist[k][j]:
            minCost = dist[i][k] + dist[k][j]
    if c > minCost:
        print((-1))
        break
    if c < minCost:
        ans += c
else:
    print(ans)