In Takahashi Kingdom, which once existed, there are N cities, and some pairs of cities are connected bidirectionally by roads.
The following are known about the road network:
 - People traveled between cities only through roads. It was possible to reach any city from any other city, via intermediate cities if necessary.
 - Different roads may have had different lengths, but all the lengths were positive integers.
Snuke the archeologist found a table with N rows and N columns, A, in the ruin of Takahashi Kingdom.
He thought that it represented the shortest distances between the cities along the roads in the kingdom.
Determine whether there exists a road network such that for each u and v, the integer A_{u, v} at the u-th row and v-th column of A is equal to the length of the shortest path from City u to City v.
If such a network exist, find the shortest possible total length of the roads.

-----Constraints-----
 - 1 \leq N \leq 300
 - If i ≠ j, 1 \leq A_{i, j} = A_{j, i} \leq 10^9.
 - A_{i, i} = 0

-----Inputs-----
Input is given from Standard Input in the following format:
N
A_{1, 1} A_{1, 2} ... A_{1, N}
A_{2, 1} A_{2, 2} ... A_{2, N}
...
A_{N, 1} A_{N, 2} ... A_{N, N}

-----Outputs-----
If there exists no network that satisfies the condition, print -1.
If it exists, print the shortest possible total length of the roads.

-----Sample Input-----
3
0 1 3
1 0 2
3 2 0

-----Sample Output-----
3

The network below satisfies the condition:
 - City 1 and City 2 is connected by a road of length 1.
 - City 2 and City 3 is connected by a road of length 2.
 - City 3 and City 1 is not connected by a road.

Difficulty: interview

Starter code:

Solutions:
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

import numpy as np

n = int(input())
a = np.array([list(map(int, input().split())) for _ in range(n)])

g = csr_matrix(a)
dist = floyd_warshall(g)

if (dist == a).all():
    sm = a.sum()

    INF = 10 ** 18 + 1
    for i in range(n):
        a[i, i] = INF

    for u in range(n):
        for v in range(n):
            if u == v:
                continue

            mn = np.min(a[u] + a[v])
            if mn == a[u, v]:
                sm -= a[u, v]

    ans = sm // 2
    print(ans)

else:
    print((-1))


import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
A = np.array(A, dtype=float) + np.diag([np.inf] * N)

useless = np.zeros((N, N), dtype=bool)
impossible = np.zeros((N, N), dtype=bool)
for via in range(N):
    # R[i][j]: i -> via -> j の距離
    R = sum(np.meshgrid(A[via], A[via]))
    useless |= R == A
    impossible |= R < A

if (impossible ^ np.eye(N, dtype=bool)).sum():
    print((-1))
else:
    print((int(A[~useless].sum() // 2)))


import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
INF = 10 ** 9
A = np.array([lr() for _ in range(N)])
np.fill_diagonal(A, INF)
answer = 0
for i in range(N-1):
    for j in range(i+1, N):
        detour = np.min(A[i]+A[j])
        if detour > A[i, j]:
            answer += A[i, j]
        elif detour < A[i, j]:
            print((-1))
            return

print(answer)
# 38


import sys
import numpy as np

read = sys.stdin.read

N, *A = list(map(int, read().split()))
A = np.array(A, np.int64).reshape(N, N)
'''
answer = 0
for i, j in product(range(N), repeat=2):
    if i < j:
        continue
    edge = A[i][j]
    for k in range(N):
        if i == k or j == k:
            continue

        tmp = A[i][k] + A[k][j]
        if tmp < edge:
            print(-1)
            return
        elif tmp == edge:
            break
    else:
        answer += edge
'''

useless = np.zeros_like(A)

for i in range(N):
    grid = A[i] + A[i, None].T
    if np.any(grid < A):
        print((-1))
        return
    grid[i] = np.inf
    grid[:, i] = np.inf

    useless |= (A == grid)

print((A[useless != 1].sum() // 2))


from numpy import *
N = int(input())
A = array([input().split() for _ in range(N)], dtype=int64).reshape(N,N)

fill_diagonal(A, 10**9)

ans = 0
for i in range(N):
  for j in range(i+1,N):
    d = min(A[i]+A[j])
    if A[i][j] < d:
      ans += A[i][j]
    elif d < A[i][j]:
      print((-1))
      return

print(ans)


import scipy.sparse as s,numpy as n
f=n.loadtxt(open(0),skiprows=1)
g=s.csgraph.dijkstra(f)
h=n.where(g,g,1)
print(int(sum(t[j]*all(t[j]<t+h[j])for i,t in enumerate(h)for j in range(i)))*(f==g).all()or-1)

import math
import numpy as np
import decimal
import collections
import itertools
import sys
import random
#Union-Find
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = list(range(self.n))
        self.rank = [1] * n
        self.count = n
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    def unite(self, x, y):
        p = self.find(x)
        q = self.find(y)
        if p == q:
            return None
        if p > q:
            p, q = q, p
        self.rank[p] += self.rank[q]
        self.par[q] = p
        self.count -= 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def size(self, x):
        return self.rank[x]
    def count(self):
        return self.count

#素数関連
def prime_numbers(x):
    if x < 2:
        return []
    prime_numbers = [i for i in range(x)]
    prime_numbers[1] = 0
    for prime_number in prime_numbers:
        if prime_number > math.sqrt(x):
            break
        if prime_number == 0:
            continue
        for composite_number in range(2 * prime_number, x, prime_number):
            prime_numbers[composite_number] = 0
    return [prime_number for prime_number in prime_numbers if prime_number != 0]
def is_prime(x):
    if x < 2:
        return False
    if x == 2 or x == 3 or x == 5:
        return True
    if x % 2 == 0 or x % 3 == 0 or x % 5 == 0:
        return False
    prime_number = 7
    difference = 4
    while prime_number <= math.sqrt(x):
        if x % prime_number == 0:
            return False
        prime_number += difference
        difference = 6 - difference
    return True
#Prime-Factorize
def prime_factorize(n):
    res = []
    while n % 2 == 0:
        res.append(2)
        n //= 2
    f = 3
    while f ** 2 <= n:
        if n % f == 0:
            res.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        res.append(n)
    return res
#nCr
mod = 10 ** 9 + 7
class counting:
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
    def per(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[n - r] % mod
#拡張Euclidの互除法
def extgcd(a, b, d = 0):
    g = a
    if b == 0:
        x, y = 1, 0
    else:
        x, y, g = extgcd(b, a % b)
        x, y = y, x - a // b * y
    return x, y, g
#BIT
class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (self.n + 1)
    def add(self, i, x):
        while i <= self.n:
            self.BIT[i] += x
            i += i & -i
    def query(self, i):
        res = 0
        while i > 0:
            res += self.BIT[i]
            i -= i & -i
        return res
#Associative Array
class AssociativeArray():
    def __init__(self, q):
        self.dic = dict()
        self.q = q
    def solve(self):
        for i in range(self.q):
            Query = list(map(int, input().split()))
            if Query[0] == 0:
                x, y, z = Query
                self.dic[y] = z
            else:
                x, y = Query
                if y in self.dic:
                    print(self.dic[y])
                else:
                    print(0)
#Floor Sum
def floor_sum(n, m, a, b):
    res = 0
    if a >= m:
        res += (n - 1) * n * (a // m) // 2
        a %= m
    if b >= m:
        res += n * (b // m)
        b %= m
    y_max = (a * n + b) // m
    x_max = y_max * m - b
    if y_max == 0:
        return res
    res += y_max * (n + (-x_max // a))
    res += floor_sum(y_max, a, m, (a - x_max % a) % a)
    return res
#Z-Algorithm
def z_algorithm(s):
    str_len = len(s)
    res = [0] * str_len
    res[str_len - 1] = str_len
    i, j = 1, 0
    while i < str_len:
        while i + j < str_len and s[i + j] == s[j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < str_len and j > res[k] + k:
            res[i + k] = res[k]
            k += 1
        i += k
        j -= k
    return res
class Manacher():
    def __init__(self, s):
        self.s = s
    def coustruct(self):
        i, j = 0, 0 
        s_len = len(self.s)
        res = [0] * s_len
        while i < s_len:
            while i - j >= 0 and i + j < s_len and self.s[i - j] == self.s[i + j]:
                j += 1
            res[i] = j
            k = 1
            while i - k >= 0 and k + res[i - k] < j:
                k += 1
            i += k
            j -= k
#mod-sqrt
def mod_sqrt(a, p):
    if a == 0:
        return 0
    if p == 2:
        return 1
    k = (p - 1) // 2
    if pow(a, k, p) != 1:
        return -1
    while True:
        n = random.randint(2, p - 1)
        r = (n ** 2 - a) % p
        if r == 0:
            return n
        if pow(r, k, p) == p - 1:
            break
    k += 1
    w, x, y, z = n, 1, 1, 0
    while k:
        if k % 2:
            y, z = w * y + r * x * z, x * y + w * z
        w, x = w * w + r * x * x, 2 * w * x
        w %= p
        x %= p
        y %= p
        z %= p
        k >>= 1
    return y
class SegmentTree:
    def __init__(self, lis, ele, op):
        self.len = len(lis)
        self.n = 1 << ((self.len - 1).bit_length())
        self.op = op
        self.ele = ele
        self.tree = self._build(lis)
    def _build(self, lis):
        res_tree = [self.ele] * (self.n - 1) + lis + [self.ele] * (self.n - self.len)
        for i in range(self.n - 2, -1, -1):
            res_tree[i] = self.op(res_tree[i * 2 + 1], res_tree[i * 2 + 2])
        return res_tree
    def __get__(self, i):
        return self.tree[self.n + i - 1]
    def update(self, i, x):
        i += self.n - 1
        self.tree[i] = x
        while i > 0:
            i -= 1
            i >>= 1
            self.tree[i] = self.op(self.tree[i * 2 + 1], self.tree[i * 2 + 2])
    def query(self, l, r):
        l +=  self.n - 1
        r += self.n - 1
        L = self.ele
        R = self.ele
        while l < r:
            if l & 1 == 0:
                L = self.op(L, self.tree[l])
                l += 1
            if r & 1 == 0:
                r -= 1
                R = self.op(R, self.tree[r])
            l -= 1
            l >>= 1
            r >>= 1
        return self.op(L, R)
def compress(l):
    n = len(l)
    sorted_list = sorted(set(l))
    d = {sorted_list[i]: i for i in range(len(sorted_list))}
    return [d[i] for i in l]
class WeightedUnionFind:
    def __init__(self, n):
        self.n = n
        self.par = list(range(n))
        self.rank = [0] * n
        self.weight = [0] * n
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            y = self.find(self.par[x])
            self.weight[x] += self.weight[self.par[x]]
            self.par[x] = y
            return y
    def unite(self, x, y, w):
        p, q = self.find(x), self.find(y)
        if self.rank[p] < self.rank[q]:
            self.par[p] = q
            self.weight[p] = w - self.weight[x] + self.weight[y]
        else:
            self.par[q] = p
            self.weight[q] = -w - self.weight[y] + self.weight[x]
            if self.rank[p] == self.rank[q]:
                self.rank[p] += 1
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def diff(self, x, y):
        return self.weight[x] - self.weight[y]
import numpy as np
n = int(input())
a = [np.array(list(map(int, input().split()))) for i in range(n)]
ans = sum([sum(a[i]) for i in range(n)]) // 2
for i in range(n):
    a[i][i] = 10 ** 9
for i in range(n - 1):
    for j in range(i + 1, n):
        m = min(a[i] + a[j])
        if m < a[i][j]:
            print(-1);return()
        if m == a[i][j]:
            ans -= a[i][j]
print(ans)

N = int(input())
dic = [0]*N
dist = [[0]*N for i in range(N)]
for i in range(N):
  dic[i] = [int(c) for c in input().split()]
  for j in range(N):
    dist[i][j] = dic[i][j]
  dic[i][i] = float('inf')

ans = 0
for i in range(N):
  for j in range(i):
    d = min(a+b for a, b in zip(dic[i],dic[j]))
    if d<dic[i][j]:
      print(-1)
      return
    elif d>dic[i][j]:
      ans += dic[i][j]
print(ans)

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

from scipy.sparse.csgraph import floyd_warshall as fw
import numpy as np
a = fw(A)
ans = 0
for i in range(N):
    a[i][i] = np.inf
for i in range(N):
    for j in range(i):
        if A[i][j]!=a[i][j]:
            print(-1)
            return
        else:
            if a[i][j] < np.min(a[i]+a[j]):
                ans += a[i][j]
print(int(ans))

import sys

import numpy as np

sys.setrecursionlimit(10000)
INF = float('inf')

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

A = np.array(A, dtype=float)

useless = np.zeros((N, N), dtype=bool)
impossible = np.zeros((N, N), dtype=bool)
for via in range(N):
    # R[i][j]: i -> via -> j の距離
    R = sum(np.meshgrid(A[via], A[via]))
    R[via] = np.inf
    R[:, via] = np.inf
    useless |= R == A
    impossible |= R < A
if impossible.sum():
    print((-1))
else:
    print((int(A[~useless].sum() // 2)))


import numpy as np
from scipy.sparse.csgraph import floyd_warshall

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

if np.any(A != floyd_warshall(A)):
    print((-1))
else:
    ans = 0
    A += np.diag([float('inf')] * N)
    for i in range(N):
        for j in range(i + 1, N):
            if np.min(A[i] + A[j]) != A[i, j]:
                ans += int(A[i, j])
    print(ans)


import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = np.array(read().split(), dtype=np.int64).reshape(N,N)

    INF = 10**15
    ans = 0
    for i in range(N):
        B = A[i,:] + A
        np.fill_diagonal(B, INF)
        B[:,i] = INF
        C = B.min(axis=1)
        C[i] = 0

        if (C < A[i,:]).sum() > 0:
            print((-1))
            return
        else:
            index = C > A[i,:]
            ans += A[i, index].sum()

    print((ans // 2))


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[List[int]]"):
    import numpy as np
    from scipy.sparse.csgraph import floyd_warshall
    A = np.array(A, dtype=np.float64)
    B = floyd_warshall(A, directed=True)
    if not np.array_equal(A, B):
        return -1
    delta = 1e-1
    _, pre = floyd_warshall(A-delta, return_predecessors=True)
    return int(A[pre == [[i]*N for i in range(N)]].sum()) // 2

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    print((solve(N, A)))

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N = int(input())
    A = np.array([list(map(int, input().split())) for i in range(N)])
    #A = [list(map(int, input().split())) for _ in range(N)]
    #A = np.array(A)

    INF = 10**10
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            #bipas = min(map(sum, zip(A[i], A[j])))
            bipas = np.min(A[i] + A[j])

            if A[i][j] > bipas:
                print((-1))
                return 0
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


def __starting_point():
    main()

__starting_point()

# 小さい距離から見ていく
# 既に作った道の範囲で、任意の2点の最短距離を持っておく
# 既存の最短距離より大きい：矛盾
# 既存の最短距離と等しい：増やしても何も変わらず
# 既存の最短距離より小さい：追加する必要あり

import numpy as np
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]

edge = []

for i in range(N):
  for j in range(i):
    edge.append((A[i][j],j,i))
edge.sort()

INF = 10**18
dist = np.full((N,N),INF,dtype=np.int64) - np.eye(N,dtype=np.int64)*INF

answer = 0
for d,x,y in edge:
  if d > dist[x,y]:
    answer = -1
    break
  if d == dist[x,y]:
    continue
  # 追加
  answer += d
  dist[x,y] = d
  dist[y,x] = d
  # 距離行列の更新
  # (i,j) -> (i,x),(x,y),(y,j)
  dist_use_xy = np.add.outer(dist[:,x], dist[:,y]) + d
  dist = np.minimum(dist,np.minimum(dist_use_xy,dist_use_xy.T))
  
print(answer)


def warshall_floyd(graph):
    num_v = len(graph)

    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph

N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
# import copy
# a_list = copy.deepcopy(graph)
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
w_graph = floyd_warshall(graph, directed=False)
result = 0
for i in range(N):
     w_graph[i][i] = float("inf")
for i in range(N):
    for j in range(i):
        if i == j:
            continue
        if w_graph[i][j] != graph[i][j]:
            print((-1))
            return
        if w_graph[i][j] < np.min(w_graph[i] + w_graph[j]):
            result += w_graph[i][j]
print((int(result)))


from numpy import *
N = int(input())
A = array([input().split() for _ in range(N)], dtype=int64)

fill_diagonal(A, 10**10)

ans = 0
for i in range(N):
  for j in range(i+1,N):
    d = min(A[i]+A[j])
    if A[i][j] < d:
      ans += A[i][j]
    elif d < A[i][j]:
      print((-1))
      return

print(ans)


import numpy as np
 
N = int(input())
A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N,N)

np.fill_diagonal(A, 10**9+1)

ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    d = np.min(A[i]+A[j])
    if d > A[i][j]:
      ans+=A[i][j]
    elif d < A[i][j]:
      print(-1)
      return

print(ans)

import numpy as np

N = int(input())
A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N,N)

INF = 10**15
np.fill_diagonal(A, INF)

ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        detour = np.min(A[i]+A[j])
        if detour > A[i][j]:
            ans+=A[i][j]
        elif detour < A[i][j]:
            print(-1)
            return
print(ans)

import numpy as np
N = int(input())
A = np.array([list(map(int,input().split())) for _ in range(N)],dtype=np.int64)

INF = 10**9+10
E = np.zeros(((N*(N-1))//2,3),dtype=np.int64)
k = 0
for i in range(N):
    for j in range(i+1,N):
        E[k,0] = A[i][j]
        E[k,1] = i
        E[k,2] = j
        k += 1
E = E[E.argsort(0)[:,0]]
B = np.ones((N,N),dtype=np.int64)*INF
ans = 0
for l,i,j in E:
    l_min = np.min(B[i]+B[j])
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    B[i][j] = l
    B[j][i] = l
print(ans)

# solution

import io
import math
import scipy.sparse as s,numpy as n

f=n.loadtxt(open(0),skiprows=1)

g=s.csgraph.dijkstra(f)

h=n.where(g,g,1)

print(int(sum(t[j]*(t[j]<t+h[j]).all()for i,t in enumerate(h)for j in range(i)))*(f==g).all()or-1)

import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

'''
Aが最短距離を表す、というのはSnukeの推測でしかない。
なので、Aを、A[v, u]が辺の重みを表しているgraphとして捉え、floyd_warshallで実際に最短距離を求め、Bとする。

B[v, u] < A[v, u]が存在したらAが最短距離を表すという推測は間違っていたことになる。
もしB[v, u] == B[v, w] + B[w, u](ただし w ≠ v, w ≠ u)となるようなwが存在したら、
Aのgraphでedge(v, u)はなくても良いことになるので、A[v, u] = A[u, v] = 0として辺を消す。(仮に辺を消しても、shortest_dist(v, u)には影響しないため)

最後に残った辺々だけをつなげてできるグラフの合計の辺の重みが答えとなる
'''

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False).astype(np.float64)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(B, np.inf)
    
    for v in range(n-1):
        for u in range(v+1, n):
            detours = B[v] + B[u]
            if np.any(detours == B[v, u]):
                A[v, u] = A[u, v] = 0

    return np.sum(A) // 2

def __starting_point():
    ans = main()
    print(ans)
__starting_point()

import numpy as np
import sys

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            n_lines = int(f.readline())
            for i in range(n_lines):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        n_lines = int(input())
        for i in range(n_lines):
            lines.append(input())
    return lines

raw_data = read_data()
tarray = []
for each in raw_data:
    tarray.append(each.split())
A = np.array(tarray, dtype='int64')
N = A.shape[0]


def Restoring_Road_Network2():

    not_available = False
    for k in range(0, N):
        for i in range(0, N):
            if(k==i): continue
            for j in range(0, N):
                if((i==j) or (j==k)): continue
                if(A[i][k] + A[k][j] < A[i][j]):
                    not_availabel = True
                if(A[i][k] + A[k][j] == A[i][j]):
                    B[i][j] = 1
                    B[j][i] = 1

    try:
        LOCAL_FLAG
        print(B)
    except NameError:
        pass

    if(not_available):
        print(-1)
    else:
        total_dis = 0
        for i in range(0, N):
            for j in range(i, N):
                if(B[i][j] == 0):
                    total_dis += A[i][j]
        print(total_dis)

def Restoring_Road_Network3():

    import scipy.sparse.csgraph as graph

    MAX = [10000000000]*N  # should be > 2*10**9
    d = np.diag(MAX)
    C = A.copy()
    C += d
    total_dis = 0
    n_path = 0
    for i in range(N-1):
        for j in range(i+1, N):
            dis_two_node = np.min(C[i] + C[j])
            if dis_two_node > C[i,j]:
                total_dis += C[i,j]
                # print(i, j)
            elif dis_two_node < C[i,j]:
                print(-1)
                return

    print(total_dis)

def AA():
    import numpy as np

    for i in range(N):
        A[i][i] = 10000000000

    result = 0
    for i in range(N-1):
        for j, d1 in enumerate(A[i][i+1:], start=i+1):
            d2 = np.min(A[i]+A[j])
            # print(A[i][i+1:])
            # print (i, j, d1, d2)
            if d1 >= d2:
                if d1 > d2:
                    print(-1)
                    return
            else:
                result += d1
    print(result)

Restoring_Road_Network3()

def RestoringRoadNetwork():
    import sys
    n = int(input())
    wf = [list(map(int, input().split())) for _ in range(n)]
    ans = 0

    # Warshall Floyd
    for i in range(n-1):
        for j in range(i+1, n):
            d = wf[i][j]
            # kを中継したときの距離
            for k in range(n):
                if k in (i, j):
                    continue
                num = wf[i][k]+wf[k][j]
                if num < d:
                    print((-1))
                    return
                elif num == d:
                    break
            else:
                ans += d
    else:
        print(ans)

def __starting_point():
    RestoringRoadNetwork()
    

__starting_point()

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

N = int(input())
A = np.asarray([[int(Aij) for Aij in input().split()] for _ in range(N)])

A2 = floyd_warshall(A, directed=False)

if np.any(A != A2):
    print(-1)
else:
    d = 0
    A += np.diag([2*10**9] * N)
    for i in range(N):
        for j in range(i + 1, N):
            if np.min(A[i] + A[j]) != A[i, j]:
                d += A[i, j]
    print(d)

import sys
import numpy as np
input = sys.stdin.readline
n = int(input())
G = np.array([list(map(int, input().split())) for _ in range(n)], dtype=float)
use = np.ones((n,n),dtype=bool)
impossible = np.zeros((n,n),dtype=bool)
for w in range(n):
    D = sum(np.meshgrid(G[w], G[w]))
    D[w] = np.inf
    D[:,w] = np.inf
    use &= ~(G == D)
    impossible |= G > D
if impossible.any():
    print(-1)
else:
    print(int(np.sum(G[use]) / 2))

import numpy as np
n=int(input())
l=[np.array(input().split(), dtype=np.int64) for _ in [0]*n]
l+=np.diag([10**10]*n)

v=0
for i in range(n-1):
  for j,d1 in enumerate(l[i][i+1:]):
    d2=np.min(l[i]+l[j+i+1])
    if d1>=d2:
      if d1>d2:
        print(-1)
        return
    else:
      v+=d1
print(v)

import sys
import numpy as np
input = sys.stdin.readline
n = int(input())
G = np.array([list(map(int, input().split())) for _ in range(n)], dtype=float)
G2 = G
for i in range(n):
    G2[i,i] = np.inf
use = np.ones((n,n),dtype=bool)
impossible = np.zeros((n,n),dtype=bool)
for w in range(n):
    D = sum(np.meshgrid(G2[w], G2[w]))
    use &= ~(G == D)
    impossible |= G > D
if impossible.sum() > n:
    print(-1)
else:
    print(int(np.sum(G[use]) / 2))

import numpy as np
N=int(input())
A=[np.array(list(map(int,input().split()))) for i in range(N)]
ans=sum([sum(A[i]) for i in range(N)])
ans//=2
for i in range(N):
    A[i][i]=10**10
def main(ans):
    for i in range(N):
        for j in range(i+1,N):
            Min=np.min(A[i]+A[j])
            if Min<A[i][j]:
                return -1
            if Min==A[i][j]:
                ans-=A[i][j]
    return ans
print(main(ans))

import numpy as np
N = int(input())
A = np.array([list(map(int, input().split())) for _ in range(N)])

for i in range(N):
    A[i][i] = 10 ** 9

ans = 0
for i in range(N):
    for j in range(i+ 1, N):
        dp = np.min(A[i] + A[j])
        if A[i][j] < dp:
            ans += A[i][j]
        elif A[i][j] > dp:
            print((-1))
            return

print (ans)


import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.float64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(B, np.inf)
    
    total_length = 0
    for v in range(n-1):
        for u in range(v+1, n):
            detours = B[v] + B[u]
            if np.all(detours > B[v, u]):
                total_length += B[v, u]

    return int(total_length)

def __starting_point():
    ans = main()
    print(ans)
__starting_point()

N, *L = map(int, open(0).read().split())
cost = []
for i,m in enumerate(zip(*[iter(L)]*N)):
  cost.append(list(m))
  cost[i][i] = 10**10
ans = 0
for i in range(N):
  for j in range(i):
    m = min(a+b for a, b in zip(cost[i],cost[j]))
    if m<cost[i][j]:
      print(-1)
      return
    if m>cost[i][j]:
      ans += cost[i][j]
print(ans)

def main():
    n=int(input())
    if n==1:
        print(0)
        return 0
    import numpy as np
    p=np.array([np.array(list(map(int,input().split()))) for _ in [0]*n])
    if n==2:
        print(p[0][1])
        return 0
    import scipy.sparse.csgraph as sp
    ans=0
    d=np.full((n,n),0)
    for i in range(n):
        for j in range(i+1,n):
            b=p[i][j]
            if b!=np.sort(p[i]+p[j])[2]:
                d[i][j],d[j][i]=b,b
                ans+=b
    s=sp.shortest_path(d)
    if (s==p).all():
        print(ans)
    else:
        print(-1)
main()

from numpy import *
N = int(input())
A = array([list(map(int,input().split())) for n in range(N)])
ans = 0

for n in range(N):
  A[n][n] = 10**9

for i in range(N):
  for j in range(i+1,N):
    dp = min(A[i]+A[j])
    if A[i][j]<dp:
      ans+=A[i][j]
    elif dp<A[i][j]:
      print(-1)
      return

print(ans)

import numpy as np
N = int(input())
A = [np.array(input().split(), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
 
result = 0
for i in range(N-1):
    for j, d1 in enumerate(A[i][i+1:], start=i+1):
        d2 = np.min(A[i]+A[j])
        if d1 >= d2:
            if d1 > d2:
                print(-1)
                return
        else:
            result += d1
print(result)

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array([lr() for i in range(N)])
INF = 10 ** 10
np.fill_diagonal(A, INF)
answer = 0
for i in range(N):
    for j in range(i+1, N):
        detour = np.min(A[i] + A[j])
        if A[i, j] < detour:
            # 最短距離としてこの道路は必要
            answer += A[i, j]
        elif A[i, j] > detour:
            print((-1))
            return

print(answer)
# 05 hint


import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array([lr() for i in range(N)])
INF = 10 ** 9
np.fill_diagonal(A, INF)
answer = 0
for i in range(N):
    for j in range(i+1, N):
        detour = np.min(A[i] + A[j])
        if A[i, j] < detour:
            # 最短距離としてこの道路は必要
            answer += A[i, j]
        elif A[i, j] > detour:
            print((-1))
            return

print(answer)
# 05 hint


def main():
    N = int(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()


from scipy.sparse.csgraph import floyd_warshall
import numpy as np
import sys
sdin = sys.stdin.readline

n = int(sdin())
graph = np.array([[0 for _ in range(n)] for _ in range(n)], dtype=float)
for i in range(n):
    graph[i] = np.array(list(map(int, sdin().split())))
    
# ワーシャルフロイドで最短距離出す
shortest = floyd_warshall(graph, directed=False)


if any([graph[i,j] != shortest[i,j] for i in range(n) for j in range(n)]):
    print(-1)
    
else:
    total = 0
    INF = float("inf")
    
    for i in range(n):
        graph[i,i] = INF
    
    for i in range(n):
        for j in range(i+1,n):
            via_k = np.min(graph[i] + graph[j])
            
            if via_k > graph[i,j]:
                total += graph[i,j]
                
    print(int(total))

N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
w_graph = floyd_warshall(graph, directed=False)
for i in range(N):
    w_graph[i][i] = float("inf")
result = 0
for i in range(N):
     w_graph[i][i] = float("inf")
for i in range(N):
    for j in range(i):
        if w_graph[i][j] != graph[i][j]:
            print((-1))
            return
        if w_graph[i][j] < np.min(w_graph[i] + w_graph[j]):
            result += w_graph[i][j]
print((int(result)))


import numpy as np
N=int(input())
A=[np.array(list(map(int,input().split()))) for i in range(N)]
ans=sum([sum(A[i]) for i in range(N)])
ans//=2
for i in range(N):
    A[i][i]=10**10
def main(ans):
    for i in range(N):
        for j in range(i+1,N):
            Min=min(A[i]+A[j])
            if Min<A[i][j]:
                return -1
            if Min==A[i][j]:
                ans-=A[i][j]
    return ans
print(main(ans))

from itertools import product
def main(): 
    with open(0) as f:
        N = int(f.readline())
        A = [list(map(int, line.split())) for line in f.readlines()]

    possible = True
    ans = 0
    r = range(N)
    for i,j in product(r, r) :
        if j <= i: continue
        for k in r:
            if k == i or k == j:
                continue
            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)


def __starting_point():
    main()
__starting_point()

import sys
from copy import deepcopy
import numpy as np
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=np.array([list(map(int,l.split())) for l in read().splitlines()])
    cost=deepcopy(a)
    for k in range(n):
        arr=np.stack([cost,[cost[k]]+np.transpose([cost[k]])])
        cost=np.amin(arr,axis=0)
    f=np.sum(cost<a)
    if f:
        print((-1))
        return
    filt=np.sum([([cost[k]]+np.transpose([cost[k]]))==cost for k in range(n)],axis=0)==2
    print((np.sum(a[filt])//2))

def __starting_point():
    main()

__starting_point()

n=int(input())
INF=float("inf")
g=[[INF]*n for _ in range(n)]
ans=0
for i in range(n):
	for j,c in enumerate(map(int,input().split())):
		if i!=j:
			g[i][j]=c
for i in range(n):
	for j in range(i):
		m=min(a+b for a,b in zip(g[i],g[j]))
		if g[i][j]>m:
			print(-1)
			return
		if g[i][j]<m:
			ans+=g[i][j]
print(ans)

import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False).astype(np.float64)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(B, np.inf)
    
    for v in range(n-1):
        for u in range(v+1, n):
            detours = B[v] + B[u]
            if np.any(detours == B[v, u]):
                A[v, u] = A[u, v] = 0
                
    return np.sum(A) // 2

def __starting_point():
    ans = main()
    print(ans)
__starting_point()

n = int(input())
import numpy as np
a = np.array([list(map(int,input().split())) for _ in range(n)])
ans = 0
for i in range(n):
    a[i][i] = 10**9+1
for i in range(n):
    for j in range(i,n):
        if i==j:
            continue
        dp = np.min(a[i]+a[j])
        if a[i][j]<dp:
            ans += a[i][j]
        elif a[i][j]>dp:
            print(-1)
            return
print(ans)

from numpy import *
N = int(input())
A = array([list(map(int,input().split())) for n in range(N)])

fill_diagonal(A, 10**10)

ans = 0
for i in range(N):
  for j in range(i+1,N):
    d = min(A[i]+A[j])
    if A[i][j] < d:
      ans += A[i][j]
    elif d < A[i][j]:
      print((-1))
      return

print(ans)


#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[List[int]]"):
    import numpy as np
    from scipy.sparse.csgraph import floyd_warshall
    A = np.array(A, dtype=np.float64)
    B = floyd_warshall(A, directed=True)
    if not np.array_equal(A, B):
        return -1
    delta = 1e-1
    _, pre = floyd_warshall(A-delta+np.identity(N)*delta, return_predecessors=True)
    return int(A[pre == [[i]*N for i in range(N)]].sum()) // 2

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    print((solve(N, A)))

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

import numpy as np

n = int(input())
a = np.array([list(map(int, input().split())) for _ in range(n)])

g = csr_matrix(a)
dist = floyd_warshall(g)

if (dist == a).all():
    sm = a.sum()
    sm //= 2

    INF = 10 ** 18 + 1
    for i in range(n):
        a[i, i] = INF

    for u in range(n):
        for v in range(u + 1, n):
            mn = np.min(a[u] + a[v])
            if mn == a[u, v]:
                sm -= a[u, v]

    print(sm)

else:
    print((-1))


import numpy as np
import sys

def read_data():
    try:
        LOCAL_FLAG
        import codecs
        import os

        lines = []
        file_path = os.path.join(os.path.dirname(__file__), 'data.dat')
        with codecs.open(file_path, 'r', 'utf-8') as f:
            n_lines = int(f.readline())
            for i in range(n_lines):
                lines.append(f.readline().rstrip("\r\n"))

    except NameError:
        lines = []
        n_lines = int(input())
        for i in range(n_lines):
            lines.append(input())
    return lines

raw_data = read_data()
tarray = []
for each in raw_data:
    tarray.append(each.split())
A = np.array(tarray, dtype='int64')
N = A.shape[0]

def Restoring_Road_Network():

    import scipy.sparse.csgraph as graph

    MAX = [10000000000]*N  # should be > 2*10**9
    d = np.diag(MAX)
    C = A.copy()
    C += d
    total_dis = 0
    n_path = 0
    for i in range(N-1):
        for j in range(i+1, N):
            dis_two_node = np.min(C[i] + C[j])
            if dis_two_node > C[i,j]:
                total_dis += C[i,j]
                # print(i, j)
            elif dis_two_node < C[i,j]:
                print(-1)
                return

    print(total_dis)

Restoring_Road_Network()

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
n = int(input())
a = np.array([[int(i) for i in input().split()] for i in range(n)])
d,ans = floyd_warshall(a,directed=False),0
if any(a[i][j]!=d[i][j] for i in range(n) for j in range(n)): ans = -1
else:
	inf = 10**10
	for i in range(n): a[i][i] = inf
	for i in range(n):
		for j in range(i+1,n):
			num = np.min(a[i]+a[j])
			if num>a[i][j]: ans+=a[i][j]
print(int(ans))

import sys
import numpy as np 
from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

n = int(sys.stdin.readline().rstrip())
A = np.array(sys.stdin.read().split(), dtype=np.float64).reshape(n, n)

def main():
    B = floyd_warshall(csr_matrix(A), directed=False).astype(np.int64)
    if np.any(B < A):
        return -1
        
    np.fill_diagonal(A, np.inf)
    
    total_length = 0
    for v in range(n-1):
        for u in range(v+1, n):
            detours = A[v] + A[u]
            if np.all(detours > B[v, u]):
                total_length += B[v, u]

    return total_length

def __starting_point():
    ans = main()
    print(ans)
__starting_point()

N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
import numpy as np
from scipy.sparse.csgraph import floyd_warshall
w_graph = floyd_warshall(graph, directed=False)
for i in range(N):
    w_graph[i][i] = float("inf")
result = 0
for i in range(N):
     w_graph[i][i] = float("inf")
for i in range(N):
    for j in range(i):
        if w_graph[i][j] != graph[i][j]:
            print((-1))
            return
        if w_graph[i][j] < np.min(w_graph[i] + w_graph[j]):
            result += w_graph[i][j]
print((int(result)))


def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]
 
    for i in range(n):
        alst[i][i]=inf
 
    sm=0
    token=0
 
    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1
 
    print(sm)
 
main()

from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def main():
    INF = 10**12
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = floyd_warshall(A)
    for i in range(N):
        A[i][i] = INF
        wf[i][i] = INF
    ans = 0
    for i in range(N):
        for j in range(N):
            if A[i][j] != wf[i][j]:
                print(-1)
                return
            if wf[i][j] < np.min(wf[i] + wf[j]):
                ans += wf[i][j]
    print(int(ans // 2))


def __starting_point():
    main()
__starting_point()

import itertools
import numpy as np
from scipy.sparse.csgraph import floyd_warshall


def main():
    N = int(input())
    matr = np.array([tuple(map(int, input().split())) for _ in range(N)], dtype=np.int64)
    way = floyd_warshall(matr).astype(int)
    if np.any(way < matr):
        print((-1))
        return

    ans = 0
    for a, b in itertools.combinations(list(range(N)), 2):
        eq = (matr[a, b] == (matr[a] + matr[:, b]))
        eq[a] = eq[b] = False
        if not np.any(eq):
            ans += matr[a, b]
    print(ans)


def __starting_point():
    main()

__starting_point()

#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[List[int]]"):
    import numpy as np
    from scipy.sparse.csgraph import floyd_warshall
    A = np.array(A, dtype=np.float64)
    B = floyd_warshall(A, directed=True)
    if not np.array_equal(A, B):
        return -1
    delta = 1e-3
    _, pre = floyd_warshall(A-delta+np.identity(N)*delta, return_predecessors=True)
    return int(A[pre == [[i]*N for i in range(N)]].sum()) // 2

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    print((solve(N, A)))

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

import numpy as np

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall


def solve():
    N = int(input())
    A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N, N)
    
    B = floyd_warshall(csr_matrix(A), directed=False)
    
    if np.any(B < A):
        print((-1))
        return
    
    np.fill_diagonal(B, np.inf)
    for i in range(N - 1):
        for j in range(i + 1, N):
            if B[i][j] == np.min(B[i] + B[j]):
                A[i][j] = A[j][i] = 0
    print((np.sum(A) // 2))


def __starting_point():
    solve()

__starting_point()

import numpy as np

n = int(input())
a = np.array([np.array(input().split(), dtype=np.uint64) for _ in range(n)], dtype=np.uint64)

for i in range(n):
  a[i,i] = 1e9 + 1

ans = 0
for u in range(n):
    for v in range(u + 1, n): 
        dist = a[u,v]
        cd = np.min(a[u] + a[v])
        if dist > cd:
            print(-1)
            return
        if dist < cd:
            ans += dist
 
print(int(ans))

from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

import numpy as np

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

a = np.array(a)

g = csr_matrix(a)
dist = floyd_warshall(g)

bl = dist == a

if bl.all():
    sm = dist.sum()
    INF = 10 ** 18 + 1
    inf = np.array([INF] * n)
    inf = np.diag(inf)
    dist += inf
    for u in range(n):
        for v in range(n):
            if u == v:
                continue

            mn = np.min(dist[u] + dist[v])
            if mn == dist[u, v]:
                sm -= dist[u, v]

    ans = int(sm) // 2
    print(ans)

else:
    print((-1))


def main():
    inf=float("inf")
    n=int(input())
    alst=[list(map(int,input().split())) for _ in range(n)]

    for i in range(n):
        alst[i][i]=inf

    sm=0
    token=0

    for i in range(n):
        for j in range(i+1,n):
            for k in range(n):
                if alst[i][k]+alst[k][j]>alst[i][j]:
                    continue
                elif alst[i][k]+alst[k][j]==alst[i][j]:
                    break
                else:
                    token=1
                    break
            else :
                sm+=alst[i][j]
    
    if token : sm=-1

    print(sm)

main()

from numpy import *
N = int(input())
A = array([input().split() for _ in range(N)], dtype=int64)

fill_diagonal(A, 10**9)

ans = 0
for i in range(N):
  for j in range(i+1,N):
    d = min(A[i]+A[j])
    if A[i][j] < d:
      ans += A[i][j]
    elif d < A[i][j]:
      print((-1))
      return

print(ans)


import heapq
INF = 10**10
n = int(input())
a = [[int(item) for item in input().split()] for _ in range(n)]
b = [[INF for _ in range(n)] for _ in range(n)]

ans = 0
for i in range(n):
    ans += sum(a[i])
    a[i][i] = INF
ans //= 2

for i in range(n):
    for j in range(i):
        bipas = min(map(sum, zip(a[i], a[j])))
        if a[i][j] > bipas:
            print(-1)
            return
        if a[i][j] == bipas:
            ans -= a[i][j]
print(ans)

import numpy as np
import scipy.sparse.csgraph as graph

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

G2 = graph.floyd_warshall(G, directed=False)

if np.any(G != G2):
    print((-1))
    return
else:
    c = [2*10**9]*N
    d = np.diag(c)
    G += d
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            two = np.min(G[i]+G[j])
            if two != G[i,j]:
                ans += G[i,j]

print(ans)


import sys

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

    INF = 10**10
    for i in range(N):
        A[i][i] = INF

    ans = 0
    for i in range(N):
        for j in range(i):
            bipas = min(list(map(sum, list(zip(A[i], A[j])))))

            if A[i][j] > bipas:
                print((-1))
                return 0
            elif A[i][j] < bipas:
                ans += A[i][j]

    print(ans)


def __starting_point():
    main()

__starting_point()

import scipy.sparse as s,numpy as n
f=n.loadtxt(open(0),skiprows=1)
g=s.csgraph.dijkstra(f)
h=n.where(g,g,1)
a=0
for i,t in enumerate(h):
  for j in range(i):
    a+=t[j]*(t[j]<t+h[j]).all()
print(int(a)*(f==g).all()or-1)

import numpy as np
from scipy.sparse.csgraph import floyd_warshall as wf
n=int(input())
s=np.array([list(map(int,input().split()))for i in range(n)])
if np.any(s!=wf(s,directed=False)):
    print(-1)
else:
    c=0
    for i in range(n):
        s[i][i]=10**10
    for i in range(n):
        for j in range(i+1,n):
            d=np.min(s[i]+s[j])
            if s[i,j]!=d:
                c+=s[i,j]
    else:
        print(c)

import numpy as np
N = int(input())
A = [np.array(input().split(), dtype=np.int64) for _ in range(N)]
ans = 0
inf = 10**10
result = 0
for i in range(N):
    A[i][i] = inf

for i in range(N-1):
    for j, d1 in enumerate(A[i][i+1:], start=i+1):
        d2 = np.min(A[i]+A[j])
        if d1 >= d2:
            if d1 > d2:
                print((-1))
                return
        else:
            result += d1

print(result)


import sys
input=sys.stdin.readline
N=int(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(map(sum,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))

import sys
from copy import deepcopy
import numpy as np
readline=sys.stdin.readline
read=sys.stdin.read

def main():
    n=int(readline())
    a=np.array([list(map(int,l.split())) for l in read().splitlines()])
    cost=deepcopy(a)
    for k in range(n):
        arr=np.stack([cost,[cost[k]]+np.transpose([cost[k]])])
        cost=np.amin(arr,axis=0)
    cost2=deepcopy(a)
    f=np.sum(cost<a)
    if f:
        print((-1))
        return
    filt=np.sum([([cost[k]]+np.transpose([cost[k]]))==cost for k in range(n)],axis=0)==2
    print((np.sum(a[filt])//2))

def __starting_point():
    main()

__starting_point()

import numpy as np
N = int(input())
A = np.array([input().split() for _ in range(N)], dtype=np.int64)

np.fill_diagonal(A, 10**9)

ans = 0
for i in range(N):
  for j in range(i+1,N):
    d = np.min(A[i]+A[j])
    if A[i][j] < d:
      ans += A[i][j]
    elif d < A[i][j]:
      print((-1))
      return

print(ans)


from scipy.sparse.csgraph import floyd_warshall
from scipy.sparse import csr_matrix

import numpy as np

n = int(input())
a = np.array([list(map(int, input().split())) for _ in range(n)])

g = csr_matrix(a)
dist = floyd_warshall(g)

if (dist == a).all():
    sm = dist.sum()

    INF = 10 ** 18 + 1
    for i in range(n):
        dist[i, i] = INF

    for u in range(n):
        for v in range(n):
            if u == v:
                continue

            mn = np.min(dist[u] + dist[v])
            if mn == dist[u, v]:
                sm -= dist[u, v]

    ans = int(sm) // 2
    print(ans)

else:
    print((-1))


def main():
    N = int(input())
    r = 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)

def __starting_point():
    main()
__starting_point()

import numpy as np

N = int(input())
A = np.array([input().split() for _ in range(N)], dtype=np.int64).reshape(N,N)

INF = 10**15
np.fill_diagonal(A, INF)

ans = 0
for i in range(N-1):
    for j in range(i+1,N):
        detour = np.min(A[i]+A[j])
        if detour > A[i][j]:
            ans+=A[i][j]
        elif detour < A[i][j]:
            print((-1))
            return
print(ans)


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

    ans = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            d = m[i][j]
            for k in range(n):
                if k in (i, j):
                    continue
                t = m[i][k] + m[k][j]
                if t < d:
                    print((-1))
                    return
                if t == d:
                    break
            else:
                ans += d
    else:
        print(ans)


def __starting_point():
    main()

__starting_point()

import sys
stdin = sys.stdin

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

import numpy as np
from scipy.sparse.csgraph import floyd_warshall

n = ni()
g = np.zeros((n,n))
for i in range(n):
    g[i,:] = np.array(list(li()))
    
    
dist = floyd_warshall(g, directed=False)

consis = True
for i in range(n):
    for j in range(n):
        if g[i,j] != dist[i,j]:
            consis = False
            break
        
if not consis:
    print(-1)
    
else:
    total = 0
    INF = float("inf")
    
    for i in range(n):
        dist[i,i] = INF
        
    for i in range(n):
        for j in range(i+1,n):
            via_k = np.min(dist[i] + dist[j])
            
            if via_k > dist[i,j]:
                total += dist[i,j]
                
    print(int(total))

import numpy as np
from scipy.sparse.csgraph import floyd_warshall
INF = 10**9

n = int(input())
a = np.array([list(map(int, input().split())) for _ in range(n)])
a_opt = floyd_warshall(a)
# for i in range(n): print(a[i], a_opt[i])

for i in range(n):
    a[i][i] = INF
    
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if a_opt[i][j] < a[i][j]:
            print((-1))
            return
        else:
            d = a[i][j]
            if d < np.min(a[i]+a[j]):
                ans += d
                
            # Straight solution, but TLE in python
            # for k in range(n):
            #     if k in [i, j]:
            #         continue
            #     elif a[i][k]+a[k][j] == d:
            #         d = 0
            # ans += d
print(ans)


#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[List[int]]"):
    import numpy as np
    from scipy.sparse.csgraph import floyd_warshall
    A = np.array(A, dtype=np.float64)
    B = floyd_warshall(A, directed=True)
    if not np.array_equal(A, B):
        return -1
    delta = 1e-7
    _, pre = floyd_warshall(A-delta+np.identity(N)*delta, return_predecessors=True)
    return int(A[pre == [[i]*N for i in range(N)]].sum()) // 2

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]  # type: "List[List[int]]"
    print((solve(N, A)))

def test():
    import doctest
    doctest.testmod()

def __starting_point():
    #test()
    main()

__starting_point()

import scipy.sparse as s,numpy as n
f=n.loadtxt(open(0),skiprows=1)
g=s.csgraph.dijkstra(f)
h=n.where(g,g,1)
print(int(sum(t[j]*(t[j]<t+h[j]).all()for i,t in enumerate(h)for j in range(i)))*(f==g).all()or-1)

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = np.array([lr() for i in range(N)])
INF = 10 ** 10
np.fill_diagonal(A, INF)
answer = 0
for i in range(N):
    for j in range(i+1, N):
        detour = np.min(A[i] + A[j])
        if A[i, j] < detour:
            # 最短距離としてこの道路は必要
            answer += A[i, j]
        elif A[i, j] > detour:
            print((-1))
            return

print(answer)
# 05 hint


from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
import numpy as np
N = int(input())
A = np.array([list(map(int, input().split())) for _ in [0]*N], dtype=np.int)
D = csgraph_from_dense(A)
D = floyd_warshall(D, directed=False)

if (A == D).all():
    ans = 0
    D += np.identity(N, int) * (1 << 60)
    for i in range(N):
        for j in range(i+1, N):
            a = np.min(D[i]+D[j])
            if a > D[i, j]:
                ans += D[i, j]
    print((int(ans)))
else:
    print((-1))