AtCoder Beginner Contest 074 - Restoring Road Network

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.

Source: atcoder | Difficulty: MEDIUM


Solutions:
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
dp = A
cnt = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		if all((dp[i][j] < dp[i][k] + dp[k][j] for k in range(N) if k != i and k != j)):
			cnt += dp[i][j]
		if any((dp[i][j] > dp[i][k] + dp[k][j] for k in range(N))):
			print(-1)
			exit()
print(cnt)


n = int(input())
a = []
for _ in range(n):
	a.append(list(map(int, input().split())))
from copy import deepcopy
b = deepcopy(a)
for i in range(n):
	for j in range(n):
		for k in range(n):
			b[j][k] = min(b[j][i] + b[i][k], b[j][k])
if a != b:
	print(-1)
	exit()
ans = 0
for i in range(n):
	b[i][i] = 10 ** 18
for i in range(n):
	for j in range(n):
		f = 1
		for k in range(n):
			if b[i][j] >= b[i][k] + b[k][j]:
				f = 0
				break
		if f:
			ans += b[i][j]
print(ans // 2)


N = int(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()
			src[i][j] = min(src[i][j], src[i][k] + src[k][j])
for i in range(N - 1):
	for j in range(i + 1, N):
		use = True
		for k in range(N):
			if k == i or k == j:
				continue
			if src[i][j] == src[i][k] + src[k][j]:
				use = False
				break
		if use:
			ans += src[i][j]
print(ans)


n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
ans = 0
cannot = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		detour = min([A[i][k] + A[k][j] for k in range(n) if k != i and k != j] + [10 ** 18])
		if detour < A[i][j]:
			cannot = 1
		elif detour > A[i][j]:
			ans += A[i][j]
if cannot:
	print(-1)
else:
	print(ans)


n = int(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)


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)


V = int(input())
A = [list(map(int, input().split())) for _ in range(V)]
ret = 0
for i in range(V):
	for j in range(i + 1, V):
		f = True
		for k in range(V):
			if i == k or j == k:
				continue
			if A[i][j] > A[i][k] + A[k][j]:
				print(-1)
				exit()
			elif A[i][j] == A[i][k] + A[k][j]:
				f = False
		if f:
			ret += A[i][j]
print(ret)


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
cnt = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		amin = 10 ** 10
		for k in range(N):
			if k != i and k != j:
				amin = min(amin, A[i][k] + A[k][j])
		if A[i][j] > amin:
			cnt = -1
			break
		elif A[i][j] < amin:
			cnt += A[i][j]
	if cnt == -1:
		break
print(cnt)


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)


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
e = [[True] * N for _ in range(N)]
ans = 0
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 A[i][j] == A[i][k] + A[k][j] and A[i][k] != 0 and (A[k][j] != 0):
				e[i][j] = False
ans = 0
for i in range(N):
	for j in range(N):
		if e[i][j]:
			ans += A[i][j]
print(ans // 2)


def main():
	N = int(input())
	A = [[int(a) for a in input().split()] for _ in range(N)]
	B = [[A[i][j] for j in range(N)] for i in range(N)]
	C = [[A[i][j] for j in range(N)] for i in range(N)]
	for k in range(N):
		for i in range(N):
			for j in range(N):
				t = B[i][k] + B[k][j]
				if t < B[i][j]:
					return -1
				if B[i][k] and B[k][j] and (t == B[i][j]):
					C[i][j] = 0
	return sum([sum([C[i][j] for j in range(i)]) for i in range(N)])
print(main())


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
f = [[True] * n for _ 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 and (k != j):
				f[i][j] = False
ans = 0
for i in range(n):
	for j in range(n):
		if f[i][j]:
			ans += a[i][j]
ans //= 2
print(ans)


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
INF = float('inf')
for i in range(N):
	A[i][i] = INF
answer = 0
for i in range(N):
	for j in range(i + 1, N):
		count = INF
		for k in range(N):
			count = min(count, A[i][k] + A[k][j])
		if A[i][j] > count:
			print(-1)
			exit()
		if A[i][j] < count:
			answer += A[i][j]
print(answer)


import sys
N = int(sys.stdin.readline().strip())
A = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(N)]
need = [[True] * N for _ in range(N)]
for i in range(N):
	for j in range(N):
		for k in range(N):
			if i == j or j == k or k == i:
				continue
			if A[i][j] + A[j][k] < A[i][k]:
				print(-1)
				exit()
			if A[i][j] + A[j][k] == A[i][k]:
				need[i][k] = False
ans = 0
for i in range(N):
	for j in range(N):
		if need[i][j]:
			ans += A[i][j]
print(ans // 2)


N = int(input())
A = [[0] for i in range(N)]
for i in range(N):
	A[i] = list(map(int, input().split()))
f = 0
r = [[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][j] > A[i][k] + A[k][j]:
				f = 1
			elif A[i][j] == A[i][k] + A[k][j] and i != k and (j != k):
				r[i][j] = 0
if f == 1:
	print('-1')
else:
	ans = 0
	for i in range(N):
		for j in range(i + 1, N):
			ans += A[i][j] * r[i][j]
	print(ans)


n = int(input())
field = [[int(v) for v in input().split()] for i in range(n)]
field_2 = [[1 for i in range(n)] for i in range(n)]
err = 0
for k in range(n):
	for i in range(n):
		for j in range(n):
			if i != j and j != k and (k != i):
				if field[i][k] + field[k][j] == field[i][j]:
					field_2[i][j] = 0
				if field[i][k] + field[k][j] < field[i][j]:
					err = 1
if err == 0:
	ans = 0
	for i in range(n):
		for j in range(n):
			ans += field[i][j] * field_2[i][j]
	print(ans // 2)
else:
	print(-1)


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
L = []
for i in range(N):
	for j in range(i + 1, N):
		L.append([A[i][j], i, j])
ans = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		for k in range(N):
			if i == k:
				continue
			if j == k:
				continue
			if A[i][j] > A[i][k] + A[k][j]:
				print(-1)
				exit()
			if A[i][j] == A[i][k] + A[k][j]:
				break
		else:
			ans += A[i][j]
print(ans)


import math, itertools, bisect, sys, copy, queue
INF = 10 ** 20

def LI():
	return [int(x) for x in sys.stdin.readline().split()]
N = int(input())
A = [LI() for _ in range(N)]
a = copy.deepcopy(A)
for k in range(N):
	for i in range(N):
		for j in range(N):
			if A[i][j] == 0 or A[i][k] == 0 or A[k][j] == 0:
				continue
			if A[i][j] > A[i][k] + A[k][j]:
				print(-1)
				exit(0)
			if A[i][j] == A[i][k] + A[k][j]:
				A[i][j] = 0
print(sum((sum(A[i]) for i in range(N))) // 2)


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
		elif a[i][j] < np.min(a[i] + a[j]):
			ans += a[i][j]
print(int(ans))


def Warshall_Floyd(edges, N):
	for (k, i, j) in itertools.product(range(N), range(N), range(N)):
		if edges[i][j] > edges[i][k] + edges[k][j]:
			return 1
	return 0
import sys
import itertools
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
if Warshall_Floyd(A, N):
	print(-1)
	sys.exit()
ans = 0
for (i, j) in itertools.product(range(N), range(N)):
	need = 1
	for k in range(N):
		if k != i and k != j and (A[i][j] == A[i][k] + A[k][j]):
			need = 0
			break
	if need:
		ans += A[i][j]
print(ans // 2)


from copy import deepcopy
N = int(input())
A = []
for i in range(N):
	A.append(list(map(int, input().split())))
B = deepcopy(A)
for u in range(N):
	for v in range(u):
		if u <= v:
			continue
		for w in range(N):
			if w == u or w == v:
				continue
			if A[u][v] > A[u][w] + A[w][v]:
				print(-1)
				exit()
			if A[u][v] == A[u][w] + A[w][v]:
				B[u][v] = 0
				B[v][u] = 0
ans = 0
for i in range(N):
	for j in range(N):
		ans += B[i][j]
print(ans // 2)


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(map(sum, 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)
main()


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))


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
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)


N = int(input())
import copy

def warshall_floyd(N):
	d = [list(map(int, input().split())) for i in range(N)]
	D = copy.deepcopy(d)
	for k in range(N):
		for i in range(N):
			for j in range(N):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	if d == D:
		return d
	else:
		return -1
E = warshall_floyd(N)
if E == -1:
	print(-1)
	exit()
for k in range(N):
	for i in range(N):
		for j in range(N):
			if E[i][j] != 0 and E[i][k] != 0 and (E[k][j] != 0):
				if E[i][j] == E[i][k] + E[k][j]:
					E[i][j] = 0
ans = 0
for i in range(N):
	ans += sum(E[i])
print(ans // 2)


N = int(input())
nums = [list(map(int, input().split())) for _ in range(N)]
for k in range(N):
	for i in range(N):
		for j in range(N):
			if nums[i][j] > nums[i][k] + nums[k][j]:
				print(-1)
				exit()
max_cost = 0
for i in range(N):
	for j in range(i + 1, N):
		flag = True
		for k in range(N):
			if k == i or k == j:
				continue
			if nums[i][j] == nums[i][k] + nums[k][j]:
				flag = False
				break
		if flag:
			max_cost += nums[i][j]
print(max_cost)


import itertools, sys
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
exists = [[True] * n for _ in range(n)]
for (k, i, j) in itertools.product(range(n), repeat=3):
	if a[i][k] + a[k][j] == a[i][j] and i != k and (k != j):
		exists[i][j] = False
	elif a[i][k] + a[k][j] < a[i][j]:
		print(-1)
		sys.exit()
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		if exists[i][j]:
			ans += a[i][j]
print(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)
	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()


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)


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
b = [[j for j in i] for i in a]
c = [n * [1] for _ 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])
			if a[i][j] == a[i][k] + a[k][j]:
				if i != j and i != k and (j != k):
					c[i][j] = 0
if a != b:
	exit(print(-1))
ans = 0
for i in range(n):
	for j in range(i):
		if c[i][j]:
			ans += a[i][j]
print(ans)


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
ans = sum((sum(a) for a in A)) // 2
removeable = set()
for k in range(N):
	for i in range(N):
		for j in range(N):
			d = A[i][k] + A[k][j]
			if A[i][j] > d:
				print(-1)
				exit()
			if A[i][j] == d and i != k and (j != k):
				removeable.add((i, j))
for i in range(N):
	for j in range(i + 1, N):
		if (i, j) in removeable:
			ans -= A[i][j]
print(ans)


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-07
	(_, 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

def main():

	def iterate_tokens():
		for line in sys.stdin:
			for word in line.split():
				yield word
	tokens = iterate_tokens()
	N = int(next(tokens))
	A = [[int(next(tokens)) for _ in range(N)] for _ in range(N)]
	print(solve(N, A))

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

def __starting_point():
	main()
__starting_point()


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
INF = 10 ** 10
E_list = []
for i in range(N):
	for j in range(i + 1, N):
		E_list.append([A[i][j], i, j])
E_list.sort()
B = [[INF] * N for _ in range(N)]
ans = 0
for (l, i, j) in E_list:
	l_min = INF
	for k in range(N):
		l_min = min(l_min, B[i][k] + B[k][j])
	if l > l_min:
		ans = -1
		break
	elif l < l_min:
		ans += l
	B[i][j] = l
	B[j][i] = l
print(ans)


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


import copy
n = int(input())
ans = 0

def warshall_floyd(d):
	for k in range(n):
		for i in range(n):
			for j in range(n):
				if i == k or j == k:
					continue
				elif d[i][j] > d[i][k] + d[k][j]:
					return -1
				elif d[i][j] == d[i][k] + d[k][j]:
					blist[i][j] = 0
	return sum([sum(l) for l in blist]) // 2
alist = []
blist = []
for i in range(n):
	a = list(map(int, input().split()))
	alist.append(copy.copy(a))
	blist.append(copy.copy(a))
ans = warshall_floyd(alist)
print(ans)


import heapq
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N):
	for j in range(N):
		via_k = float('inf')
		for k in range(N):
			if A[i][j] > A[i][k] + A[k][j]:
				print(-1)
				exit()
			if k == i or k == j:
				continue
			via_k = min(via_k, A[i][k] + A[k][j])
		if i <= j:
			continue
		if A[i][j] < via_k:
			ans += A[i][j]
print(ans)


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
	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]
			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])
			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
	for i in range(n - 1):
		for j in range(i + 1, n):
			d = wf[i][j]
			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()


n = int(input())
wf = []
for _ in range(n):
	wf.append(list(map(int, input().split())))
cnt = [[0 for _ in range(n)] for _ in range(n)]
for k in range(n):
	for i in range(n):
		for j in range(n):
			if wf[i][j] > wf[i][k] + wf[k][j]:
				print(-1)
				exit()
			elif wf[i][j] == wf[i][k] + wf[k][j]:
				cnt[i][j] += 1
ans = 0
for i in range(n):
	for j in range(n):
		if cnt[i][j] <= 2:
			ans += wf[i][j]
print(ans // 2)


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 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] = 1000000000.0 + 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))


(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)
			exit()
		if m > cost[i][j]:
			ans += cost[i][j]
print(ans)


import sys
input = lambda : sys.stdin.readline().rstrip()
n = int(input())
table = []
for i in range(n):
	table.append([int(i) for i in input().split()])
Chk = True
for k in range(n):
	for i in range(n):
		for j in range(n):
			if table[i][k] + table[k][j] < table[i][j]:
				Chk = False
				table[i][j] = table[i][k] + table[k][j]
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		C = True
		for k in range(n):
			if k == i or k == j:
				continue
			elif table[i][k] + table[k][j] == table[i][j]:
				C = False
		if C:
			ans += table[i][j]
print(ans if Chk else -1)


N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
ans = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		direct = A[i][j]
		for k in range(N):
			if k == i or k == j:
				continue
			ind = A[i][k] + A[k][j]
			if direct > ind:
				print(-1)
				exit()
			elif direct == ind:
				break
		else:
			ans += direct
print(ans)


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


N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
check = [[1] * N for _ in range(N)]
for i in range(N):
	for j in range(N):
		if i == j:
			continue
		for k in range(N):
			if i == k or j == k:
				pass
			elif d[i][j] > d[i][k] + d[k][j]:
				print(-1)
				exit()
			elif d[i][j] == d[i][k] + d[k][j]:
				check[i][j] = 0
ans = 0
for i in range(N):
	for j in range(N):
		ans += d[i][j] * check[i][j]
print(ans // 2)


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 sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
N = int(input())
INF = 10 ** 10
cost = [[INF] * N for _ in range(N)]
for i in range(N):
	C = list(map(int, input().split()))
	for j in range(N):
		cost[i][j] = C[j]
	cost[i][i] = INF
ans = 0
for j in range(N):
	for k in range(j + 1, N):
		mn = INF
		for i in range(N):
			mn = min(mn, cost[j][i] + cost[i][k])
		if cost[j][k] > mn:
			print(-1)
			exit()
		elif cost[j][k] < mn:
			ans += cost[j][k]
print(ans)


import copy
n = int(input())
l = [list(map(int, input().split())) for i in range(n)]
l1 = 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()
			elif l[i][j] == l[i][k] + l[k][j]:
				if i != k and k != j:
					l1[i][j] = 0
ans = 0
for i in l1:
	for j in i:
		ans += j
print(ans // 2)


import copy
import sys
INF = 2 ** 120
n = int(input())
d = [[] for j in range(n)]
for j in range(n):
	d[j] = [int(i) for i in input().split()]
ans = sum([sum(d[i]) for i in range(n)])
minus = [[0] * n for i in range(n)]
for k in range(n):
	for i in range(n):
		for j in range(n):
			if d[i][j] > d[i][k] + d[k][j]:
				print('-1')
				sys.exit()
			if d[i][j] == d[i][k] + d[k][j] and i != k and (j != k):
				minus[i][j] = 1
for i in range(n):
	for j in range(n):
		if minus[i][j]:
			ans -= d[i][j]
print(ans // 2)


N = int(input())
Map = [list(map(int, input().split())) for i in range(N)]
ans = sum([sum(Map[i]) for i in range(N)])
for k in range(N):
	for i in range(N):
		for j in range(N):
			if Map[i][k] + Map[k][j] < Map[i][j]:
				print(-1)
				exit()
for i in range(N):
	for j in range(N):
		for k in range(N):
			if i == k or j == k:
				continue
			if Map[i][k] + Map[k][j] == Map[i][j]:
				ans -= Map[i][j]
				break
print(ans // 2)


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)


N = int(input())
(A, B, Ans) = ([], [], 0)
for i in range(N):
	x = list(map(int, input().split()))
	A.append(x[:])
	B.append(x[:])
for k in range(N):
	for i in range(N):
		for j in range(N):
			B[i][j] = min(B[i][j], B[i][k] + B[k][j])
if A != B:
	print(-1)
else:
	for i in range(N):
		for j in range(i + 1, N):
			exists = True
			for k in range(N):
				if k not in (i, j) and B[i][j] == B[i][k] + B[k][j]:
					exists = False
			if exists:
				Ans += B[i][j]
	print(Ans)


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)
main()


import sys
import copy
n = int(input())
dist = [list(map(int, input().split())) for _ in range(n)]
e = copy.deepcopy(dist)
for k in range(n):
	for i in range(n):
		for j in range(n):
			if dist[i][j] > dist[i][k] + dist[k][j]:
				print(-1)
				sys.exit()
			if i != j and i != k and (j != k) and (dist[i][j] == dist[i][k] + dist[k][j]):
				e[i][j] = float('inf')
ans = 0
for i in range(n):
	for j in range(n):
		if e[i][j] != float('inf'):
			ans += dist[i][j]
print(ans // 2)


N = int(input())
A = [[int(i) for i in input().split()] for i in range(N)]
ans = 0
for i in range(N):
	for j in range(i + 1, N):
		flag = True
		for k in range(N):
			if j == k or i == k:
				continue
			if A[i][j] > A[i][k] + A[k][j]:
				print(-1)
				exit()
			if A[i][j] == A[i][k] + A[k][j]:
				flag = False
		if flag:
			ans += A[i][j]
print(ans)


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
	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)


N = int(input())
As = [list(map(int, input().split())) for _ in range(N)]
flag1 = False
ans = 0
for i in range(N):
	for j in range(i + 1, N):
		flag2 = True
		for k in range(N):
			if k == i or k == j:
				continue
			if As[i][k] + As[k][j] < As[i][j]:
				flag1 = True
				break
			elif As[i][k] + As[k][j] == As[i][j]:
				flag2 = False
		if flag2:
			ans += As[i][j]
		if flag1:
			break
	if flag1:
		break
if not flag1:
	print(ans)
else:
	print(-1)


import sys
from copy import deepcopy
N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
B = deepcopy(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 A[i][k] + A[k][j] < A[i][j]:
				print(-1)
				sys.exit()
			elif A[i][k] + A[k][j] == A[i][j]:
				B[i][j] = 0
ans = sum((sum((B[i][j] for j in range(N))) for i in range(N))) // 2
print(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) + 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 = 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 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):
	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
print(ans)


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
B = [A[i][:] for i in range(N)]
C = [A[i][:] for i in range(N)]
for k in range(N):
	for i in range(N):
		for j in range(N):
			if k == i or k == j:
				continue
			if B[i][k] + B[k][j] <= B[i][j]:
				A[i][j] = -1
				B[i][j] = B[i][k] + B[k][j]
ans = 0
for i in range(N):
	for j in range(N):
		if B[i][j] != C[i][j]:
			print(-1)
			exit()
		if A[i][j] != -1:
			ans += A[i][j]
			A[i][j] = -1
			A[j][i] = -1
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)
main()


n = int(input())
dp = [[int(x) for x in input().split()] for y in range(n)]
del_l = []
ans = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		for k in range(n):
			if k in (i, j):
				continue
			if dp[i][j] > dp[i][k] + dp[k][j]:
				print('-1')
				exit()
			elif dp[i][j] == dp[i][k] + dp[k][j]:
				break
		else:
			ans += dp[i][j]
print(ans)


from copy import deepcopy
n = int(input())
INF = 10 ** 12
A = []
for i in range(n):
	A.append(list(map(int, input().split())))
B = [[1] * n for _ in range(n)]
G = deepcopy(A)
for k in range(n):
	for i in range(n):
		for j in range(n):
			G[i][j] = min(G[i][j], G[i][k] + G[k][j])
			if not (i == j or j == k or k == i):
				if G[i][j] == G[i][k] + G[k][j]:
					B[i][j] = 0
if A == G:
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			ans += G[i][j] * B[i][j]
	print(ans)
else:
	print(-1)


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)


N = int(input())
A = [list(map(int, input().split())) for _ 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):
	for j in range(i + 1, N):
		f = True
		for k in range(N):
			if k == i or k == j:
				continue
			if A[i][j] == A[i][k] + A[k][j]:
				f = False
				break
		if f:
			ans += A[i][j]
print(ans)


N = int(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):
	for j in range(N):
		if all([A[i][j] < A[i][k] + A[k][j] or k == i or k == j for k in range(N)]):
			ans += A[i][j]
print(ans // 2)


import sys
input = sys.stdin.readline
n = int(input())
wf = [list(map(int, input().split())) for i in range(n)]
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		use = True
		for h in range(n):
			if h != i and h != j and (wf[i][j] > wf[i][h] + wf[h][j]):
				print(-1)
				exit()
			if h != i and h != j and (wf[i][j] == wf[i][h] + wf[h][j]):
				use = False
		if use:
			ans += wf[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.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())
A = []
for _ in range(N):
	A.append(list(map(int, input().split())))
ans = 0
for i in range(N):
	for j in range(N):
		used = True
		for k in range(N):
			if i == k or j == k:
				continue
			tmp = A[i][k] + A[k][j]
			if A[i][j] > tmp:
				print(-1)
				exit()
			if A[i][j] == tmp:
				used = False
		if used:
			ans += A[i][j]
print(ans // 2)


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)
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)


import math
import numpy as np
import decimal
import collections
import itertools
import sys
import random

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

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
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

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)

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

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)

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

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

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)


import sys
input = sys.stdin.buffer.readline

def main():
	N = int(input())
	edge = [list(map(int, input().split())) for _ in range(N)]
	for i in range(N):
		edge[i][i] = 10 ** 10
	ans = 0
	for i in range(N):
		for j in range(i):
			d = min((a + b for (a, b) in zip(edge[i], edge[j])))
			if edge[i][j] > d:
				print(-1)
				exit()
			elif edge[i][j] < d:
				ans += edge[i][j]
	print(ans)
main()


from copy import deepcopy
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
B = deepcopy(A)
s = 0
for i in range(N):
	via = A[i]
	for j in range(N):
		start = A[j]
		for k in range(N):
			if start[k] > start[i] + via[k]:
				print(-1)
				exit()
for j in range(N):
	for k in range(j):
		a = A[j][k]
		for i in range(N):
			if i in {j, k}:
				continue
			if a == A[j][i] + A[i][k]:
				break
		else:
			s += a
print(s)


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)


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

def chk():
	v = 0
	for j in range(n):
		for i in range(n):
			f = True
			for k in range(n):
				if l[i][j] > l[i][k] + l[k][j]:
					return -1
				if l[i][j] == l[i][k] + l[k][j] and i != k and (k != j):
					f = False
			if f:
				v += l[i][j]
	return v // 2
print(chk())


def main():
	n = int(input())
	a = [[int(x) for x in 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)
					return
	ret = 0
	for i in range(n):
		for j in range(i):
			for k in range(n):
				if k == i or k == j:
					continue
				if a[i][j] == a[i][k] + a[k][j]:
					break
			else:
				ret += a[i][j]
	print(ret)
main()


inf = float('inf')
N = int(input())
A = []
for _ in range(N):
	a = [int(s) for s in input().split()]
	A.append(a)
d = [a[:] for a in A]
ans = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		dmin = min([inf] + [d[i][k] + d[k][j] for k in range(N) if k not in (i, j)])
		if d[i][j] > dmin:
			print(-1)
			exit()
		if d[i][j] != dmin:
			ans += d[i][j]
print(ans)


n = int(input())
d = []
for i in [0] * n:
	d.append([int(x) for x in input().split()])
from itertools import product
ans = 0
for (i, j) in product(range(n), range(n)):
	flag = 0
	for k in range(n):
		if d[i][j] > d[i][k] + d[k][j]:
			print(-1)
			import sys
			sys.exit()
		if d[i][j] == d[i][k] + d[k][j] and (k != i and k != j and (i != j)):
			flag = 1
	if flag == 0:
		ans += d[i][j]
print(ans // 2)


N = int(input())
li = [[int(it) for it in input().split()] for i in range(N)]
iru = [[1] * N for i in range(N)]
Flag = True
s = 0
for i in range(N):
	for j in range(N):
		for k in range(N):
			if i == j or j == k or k == i:
				continue
			if li[i][j] > li[i][k] + li[k][j]:
				Flag = False
			if li[i][j] == li[i][k] + li[k][j]:
				iru[i][j] = 0
for i in range(N):
	for j in range(N):
		if i < j:
			s += iru[i][j] * li[i][j]
print(s if Flag else -1)


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)
			exit()
		if g[i][j] < m:
			ans += g[i][j]
print(ans)


n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
ans = 0
for s in range(n):
	for g in range(n):
		b = 0
		for via in range(n):
			if A[s][g] > A[s][via] + A[via][g]:
				print(-1)
				exit()
			if A[s][g] == A[s][via] + A[via][g]:
				b += 1
		if b == 2:
			ans += A[s][g]
print(ans // 2)


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
ans = 0
for i in range(N):
	for j in range(i + 1, N):
		ans += A[i][j]
m = set()
for k in range(N):
	for i in range(N):
		if k == i:
			continue
		for j in range(i + 1, N):
			if k == j:
				continue
			a = A[i][j]
			b = A[i][k] + A[k][j]
			if b == a:
				m.add((i, j))
			elif b < a:
				print(-1)
				exit()
for (i, j) in m:
	ans -= A[i][j]
print(ans)


n = int(input())
mat = [list(map(int, input().split())) for _ in range(n)]
ans = 0
d = [[1] * n for _ in range(n)]
for i in range(n):
	for (j, c2) in enumerate((row[i] for row in mat)):
		for (k, (c1, c3)) in enumerate(zip(mat[j], mat[i])):
			if c1 > c2 + c3:
				print(-1)
				exit(0)
			elif i != j and i != k and (c1 == c2 + c3):
				d[j][k] = 0
for i in range(n):
	for j in range(n):
		if d[i][j]:
			ans += mat[i][j]
print(ans // 2)


def warshall_floyd(G):
	import copy
	ret = copy.deepcopy(G)
	for k in range(N):
		for i in range(N):
			for j in range(N):
				ret[i][j] = min(ret[i][j], ret[i][k] + ret[k][j])
	return ret
N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
(W, ans) = (warshall_floyd(A), 0)
if A == W:
	for i in range(N):
		for j in range(N):
			if sum([A[i][j] == A[i][k] + A[k][j] for k in range(N) if k != i and k != j]) == 0:
				ans += A[i][j]
	print(ans // 2)
else:
	print(-1)


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()


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()


import copy
N = int(input())
graph = []
for i in range(N):
	graph.append(list(map(int, input().split())))
dp = copy.deepcopy(graph)
for k in range(N):
	for i in range(N):
		for j in range(N):
			dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
res = 0
for i in range(N):
	for j in range(N):
		if dp[i][j] < graph[i][j]:
			print(-1)
			exit()
		elif dp[i][j] == graph[i][j]:
			flg = True
			for k in range(N):
				if k != i and k != j and (dp[i][j] == dp[i][k] + dp[k][j]):
					flg = False
			if flg:
				res += dp[i][j]
print(res // 2)


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
flag = [[True] * n for _ in range(n)]
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 a[i][j] > a[i][k] + a[k][j]:
				print(-1)
				exit()
			if a[i][j] == a[i][k] + a[k][j]:
				flag[i][j] = False
				flag[j][i] = False
ans = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		if flag[i][j]:
			ans += a[i][j]
print(ans)


def resolve():
	N = int(input())
	A = [list(map(int, input().split())) for _ in range(N)]
	ans = 0
	for src in range(N - 1):
		for dst in range(src + 1, N):
			mintotal = float('inf')
			for trans in range(N):
				if trans == src or trans == dst:
					continue
				mintotal = min(mintotal, A[src][trans] + A[trans][dst])
			if A[src][dst] > mintotal:
				print(-1)
				return
			if A[src][dst] < mintotal:
				ans += A[src][dst]
	print(ans)
if '__main__' == __name__:
	resolve()


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)


INF = 10 ** 12
N = int(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)


N = int(input())
inf = float('inf')
A = [list(map(int, input().split())) for _ in range(N)]

def calc():
	ans = 0
	for i in range(N):
		for j in range(N):
			used = True
			for k in range(N):
				if i == k or k == j:
					continue
				if A[i][j] > A[i][k] + A[k][j]:
					return -1
				elif A[i][j] == A[i][k] + A[k][j]:
					used = False
			if used:
				ans += A[i][j]
	return ans // 2
print(calc())


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
from copy import deepcopy as dc
input = sys.stdin.buffer.readline
N = int(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)


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
cnt = 0
for k in range(n):
	for i in range(n - 1):
		for j in range(i + 1, n):
			if a[i][j] > a[i][k] + a[k][j]:
				print(-1)
				exit(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
			elif a[i][j] == a[i][k] + a[k][j]:
				cnt += a[i][j]
				break
tot = sum((sum(x) for x in a)) // 2
print(tot - cnt)


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


from collections import deque
import sys, copy, itertools, heapq
input = sys.stdin.readline
n = int(input())
MAP = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
	MAP[i][i] = 10 ** 9
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		MAPP = [0] * n
		for k in range(n):
			MAPP[k] = MAP[i][k] + MAP[j][k]
		d = min(MAPP)
		if MAP[i][j] < d:
			ans += MAP[i][j]
		elif d < MAP[i][j]:
			print(-1)
			exit()
print(ans)


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 _ 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)


n = int(input())
dist = [list(map(int, input().split())) for i in range(n)]
use = [[True for i in range(n)] for j in range(n)]
ans = 0
for i in range(n):
	for j in range(n):
		for k in range(n):
			if dist[j][k] > dist[j][i] + dist[i][k]:
				print(-1)
				exit()
			elif j != i and j != k and (i != k) and (dist[j][k] == dist[j][i] + dist[i][k]):
				use[j][k] = False
for i in range(n):
	for j in range(n):
		if use[i][j]:
			ans += dist[i][j]
print(ans // 2)


n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
length = 0
for i in range(n):
	for j in range(n):
		route = 10000000000
		for k in range(n):
			if k == i or k == j:
				continue
			route = min(route, a[i][k] + a[k][j])
			if route < a[i][j]:
				print(-1)
				exit()
		if route > a[i][j]:
			length += a[i][j]
print(int(length / 2))


def Warshall_Floyd(edges, N):
	import copy
	d = copy.deepcopy(edges)
	for k in range(N):
		for i in range(N):
			for j in range(N):
				d[i][j] = min(d[i][j], d[i][k] + d[k][j])
	return d
import sys
N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
B = Warshall_Floyd(A, N)
if A != B:
	print(-1)
	sys.exit()
ans = 0
for i in range(N):
	for j in range(i):
		need = 1
		for k in range(N):
			if k != i and k != j:
				if A[i][j] == A[i][k] + A[k][j]:
					need = 0
		ans += need * A[i][j]
print(ans)


N = int(input())
A = []
for i in range(N):
	As = list(map(int, input().split()))
	A.append(As)
r = 0
for i in range(N):
	for j in range(i + 1, N):
		ok = False
		for k in range(N):
			if A[i][j] > A[i][k] + A[k][j]:
				print(-1)
				exit()
			if A[i][j] == A[i][k] + A[k][j] and k != i and (k != j):
				ok = True
		if not ok:
			r += A[i][j]
print(r)


import sys
input = sys.stdin.readline
n = int(input())
dist = [list(map(int, input().split())) for i in range(n)]
ans = 0
for arr in dist:
	ans += sum(arr)
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i != j and j != k and (k != i):
				if dist[i][k] + dist[k][j] == dist[i][j] and dist[i][k] != 0 and (dist[k][j] != 0):
					ans -= dist[i][j]
					break
				elif dist[i][k] + dist[k][j] < dist[i][j] and dist[i][k] != 0 and (dist[k][j] != 0):
					print(-1)
					exit()
print(ans // 2)


def solve(V, G):
	ans = 0
	for i in range(V - 1):
		for j in range(i + 1, V):
			direct = G[i][j]
			for k in range(V):
				if k == i or k == j:
					continue
				ind = G[i][k] + G[k][j]
				if direct > ind:
					return -1
				elif direct == ind:
					break
			else:
				ans += direct
	return ans

def main():
	V = int(input())
	G = [[int(i) for i in input().split()] for i in range(V)]
	print(solve(V, G))
main()


def main():
	N = int(input())
	A = [list(map(int, input().split())) for _ in range(N)]
	r = 0
	for i in range(N):
		for j in range(i + 1, N):
			for k in range(N):
				if k == i or k == j:
					continue
				if A[i][k] + A[k][j] < A[i][j]:
					return -1
				if A[i][k] + A[k][j] == A[i][j]:
					break
			else:
				r += A[i][j]
	return r
print(main())


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)


def warshall_floyd(G, n):
	global c
	for i in range(n):
		for j in range(n):
			b = 1
			for k in range(n):
				if j == k or i == k:
					continue
				if G[i][j] == G[i][k] + G[k][j]:
					b = 0
				elif G[i][j] > G[i][k] + G[k][j]:
					print(-1)
					exit()
			if b == 1:
				c += G[i][j]
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
c = 0
warshall_floyd(a, n)
print(c // 2)


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]
			t = min((m[i][k] + m[k][j] if k != i and k != j else d + 1 for k in range(n)))
			if t < d:
				print(-1)
				exit()
			if d < t:
				ans += d
	print(ans)
main()


n = int(input())
a = [[int(i) for i in input().split()] for _ in range(n)]
d = [a[i][:] for i in range(n)]
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])
ans = 0
for i in range(n):
	for j in range(n):
		if a[i][j] > d[i][j]:
			ans = -2
			break
		for k in range(n):
			if i == k or j == k:
				continue
			if d[i][j] == d[i][k] + d[k][j]:
				break
		else:
			ans += d[i][j]
	else:
		continue
	break
ans //= 2
print(ans)


import sys
input = sys.stdin.readline

def main():
	N = int(input())
	A = [tuple(map(int, input().split())) for i in range(N)]
	ans = 0
	for i in range(N):
		for j in range(i + 1, N):
			ans += A[i][j]
			for k in range(N):
				if i != k and j != k:
					if A[i][j] > A[i][k] + A[k][j]:
						print(-1)
						exit()
					elif A[i][j] == A[i][k] + A[k][j]:
						ans -= A[i][j]
						break
	print(ans)
main()


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)


def main():
	N = int(input())
	l = []
	for i in range(N):
		a = list(map(int, input().split()))
		l.append(a)
	ans = 0
	for i in range(N):
		for j in range(i + 1, N):
			if i == j:
				continue
			for k in range(N):
				if k == i or k == j:
					continue
				if l[i][j] == l[i][k] + l[k][j]:
					break
				if l[i][j] > l[i][k] + l[k][j]:
					return -1
			else:
				ans += l[i][j]
	return ans
print(main())


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()


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)


import copy

def warshall_floyd(d, n):
	D = copy.deepcopy(d)
	for k in range(n):
		for i in range(n):
			for j in range(n):
				if i == k or k == j:
					continue
				if d[i][k] + d[k][j] < d[i][j]:
					return -1
				elif d[i][k] + d[k][j] == d[i][j]:
					D[i][j] = 0
	ans = sum([sum(i) for i in D])
	assert not ans % 2
	return ans // 2
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
ans = warshall_floyd(a, n)
print(ans)


n = int(input())
dp = [list(map(int, input().split())) for _ in range(n)]
ans = sum([sum(i) for i in dp])
for i in range(n):
	for j in range(n):
		if dp[i][j] == 0:
			continue
		a = 0
		for k in range(n):
			if dp[i][k] == 0:
				continue
			if j == k:
				continue
			if dp[i][k] + dp[k][j] < dp[i][j]:
				print(-1)
				exit()
			if dp[i][k] + dp[k][j] == dp[i][j]:
				a = 1
		if a == 1:
			ans -= dp[i][j]
print(ans // 2)


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)])
	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 = 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()


import copy
N = int(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)


N = int(input())
A = list((list(map(int, input().split())) for i in range(N)))
B = [A[i][:] for i in range(N)]
ans = 0
for i in range(N):
	for j in range(i + 1, N):
		flag = True
		for k in range(N):
			if not i != k != j:
				continue
			if A[i][j] == A[i][k] + A[j][k]:
				flag = False
			elif A[i][j] > A[i][k] + A[j][k]:
				print(-1)
				exit()
		if flag:
			ans += A[i][j]
print(ans)


import copy
n = int(input())
a = []
ans = 0
for _ in range(n):
	b = list(map(int, input().split()))
	ans += sum(b)
	a.append(b)
c = copy.deepcopy(a)
for i in range(n):
	for j in range(n):
		ch = 0
		for k in range(n):
			if c[i][j] == c[i][k] + c[k][j] and ch == 0 and (i != k) and (j != k):
				ans -= c[i][j]
				ch += 1
			c[i][j] = min(c[i][j], c[i][k] + c[k][j])
if a == c:
	print(ans // 2)
else:
	print(-1)


import sys
n = int(input())
road = [0] * n
for i in range(n):
	road[i] = [int(x) for x in input().split()]
road_judge = [[True] * n for i in range(n)]
for k in range(n):
	for i in range(n):
		for j in range(n):
			if road[i][j] > road[i][k] + road[k][j]:
				print(-1)
				sys.exit()
			if road[i][j] == road[i][k] + road[k][j] and i != k and (j != k):
				road_judge[i][j] = False
ans = 0
for i in range(n):
	for j in range(n):
		if road_judge[i][j]:
			ans += road[i][j]
print(ans // 2)


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


n = int(input())
ary = [list(map(int, input().split())) for _ in range(n)]
ans = sum([sum(i) for i in ary])
for i in range(n):
	for j in range(n):
		flag = 0
		for k in range(n):
			if j == k or i == k:
				continue
			if ary[i][j] > ary[i][k] + ary[k][j]:
				print(-1)
				exit()
			if ary[i][j] == ary[i][k] + ary[k][j]:
				flag = 1
		if flag:
			ans -= ary[i][j]
print(ans // 2)


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

def sol():
	for k in range(N):
		for i in range(N):
			for j in range(N):
				d = A[i][k] + A[k][j]
				if d < A[i][j]:
					return -1
	ret = 0
	for i in range(N):
		for j in range(i + 1, N):
			for k in range(N):
				if k == i or k == j:
					continue
				if A[i][k] + A[k][j] == A[i][j]:
					break
			else:
				ret += A[i][j]
	return ret
print(sol())


N = int(input())
A = [[int(x) for x in input().split()] for _ in range(N)]
flag = True
for k in range(N):
	for i in range(N):
		for j in range(i):
			if A[i][j] > A[i][k] + A[k][j]:
				flag = False
				break
		if not flag:
			break
	if not flag:
		break
ans = 0
if flag:
	for i in range(N):
		for j in range(i):
			flag = True
			for k in range(N):
				if k != i and k != j:
					if A[i][j] == A[i][k] + A[k][j]:
						flag = False
						break
			if flag:
				ans += A[i][j]
	print(ans)
else:
	print(-1)


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

def judge():
	s = 0
	for i in range(N):
		for j in range(i + 1, N):
			for k in range(N):
				if i == k or j == k:
					continue
				if A[i][k] + A[k][j] < A[i][j]:
					return -1
				elif A[i][k] + A[k][j] == A[i][j]:
					s += A[i][j]
					break
	tot = 0
	for i in range(N):
		for j in range(i + 1, N):
			tot += A[i][j]
	return tot - s
print(judge())


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)


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 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))


N = int(input())
A = [[] for i in range(0, N)]
for i in range(0, N):
	A[i] = list(map(int, input().split()))
count = 0
for i in range(0, N):
	for j in range(0, N):
		for k in range(0, N):
			if A[i][j] > A[i][k] + A[k][j]:
				print(-1)
				exit()
			elif A[i][j] == A[i][k] + A[k][j] and k != i and (k != j):
				break
		else:
			count += A[i][j]
print(count // 2)


n = int(input())
mat = []
for _ in range(n):
	mat.append(list(map(int, input().split())))
d = [[False] * n for _ in range(n)]
for k in range(n):
	for i in range(n):
		for j in range(n):
			if mat[i][j] > mat[i][k] + mat[k][j]:
				print(-1)
				exit()
			if mat[i][j] == mat[i][k] + mat[k][j] and mat[i][k] > 0 and (mat[k][j] > 0):
				d[i][j] = True
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		if not d[i][j]:
			ans += mat[i][j]
print(ans)


N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
ans = 0
for i in range(N):
	for j in range(i + 1, N):
		dij = A[i][j]
		res = True
		for k in range(N):
			if k in [i, j]:
				continue
			dikj = A[i][k] + A[k][j]
			if dij > dikj:
				print(-1)
				quit()
			elif dij == dikj:
				res = False
		if res:
			ans += dij
print(ans)


N = int(input())
A = []
for i in range(N):
	a = list(map(int, input().split()))
	A.append(a)
ans = 0
for i in range(N):
	for j in range(N):
		ans += A[i][j]
		for k in range(i + 1, N):
			if A[i][j] + A[j][k] < A[i][k]:
				print(-1)
				quit()
ans //= 2
for i in range(N):
	for k in range(i + 1, N):
		for j in range(N):
			if i == j or j == k:
				continue
			if A[i][j] + A[j][k] == A[i][k]:
				ans -= A[i][k]
				break
print(ans)


def i1():
	return int(input())

def i2():
	return [int(i) for i in input().split()]
n = i1()
a = []
e = 0
for i in range(n):
	a.append(i2())
	e += sum(a[-1])
d = [x[:] for x in a]
dd = [x[:] for x in a]
c = 0
for i in range(n):
	for j in range(n):
		for k in range(n):
			if a[j][k] > d[j][i] + d[i][k]:
				c = -1
			elif a[j][k] == d[j][i] + d[i][k] and d[j][i] > 0 and (d[i][k] > 0):
				dd[j][k] = 0
			d[j][k] = min(d[j][k], d[j][i] + d[i][k])
if c < 0:
	print(-1)
else:
	s = 0
	for i in range(n):
		for j in range(i, n):
			s += dd[i][j]
	print(s)


N = int(input())
A = [[0 for _ in range(N + 1)]]
for _ in range(N):
	a = list(map(int, input().split()))
	a.insert(0, 0)
	A.append(a)
tot = 0
for i in range(1, N):
	for j in range(i, N + 1):
		tot += A[i][j]
for i in range(1, N):
	for j in range(i + 1, N + 1):
		for k in range(1, N + 1):
			if k != i and k != j:
				if A[i][j] > A[i][k] + A[k][j]:
					tot = -1
					break
				elif A[i][j] == A[i][k] + A[k][j]:
					tot -= A[i][j]
					break
		if tot < 0:
			break
	if tot < 0:
		break
print(tot)


N = int(input())
A = [list(map(int, input().split())) for _ in range(N)]
cnt = 0
for i in range(N):
	for j in range(N):
		cnt += A[i][j]
flg = 0
B = [[0 for _ in range(N)] for _ 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]:
				flg = -1
				break
			elif A[i][j] == A[i][k] + A[k][j] and A[i][k] * A[k][j] > 0 and (B[i][j] == 0):
				cnt -= A[i][j]
				B[i][j] = 1
		if flg == -1:
			break
	if flg == -1:
		break
if flg == -1:
	print(-1)
else:
	print(cnt // 2)


import sys
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
inf = float('inf')
data = [[inf] * n for i in range(n)]
ans = 0
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i == k or j == k:
				continue
			if a[i][j] == a[i][k] + a[k][j]:
				break
			elif a[i][j] > a[i][k] + a[k][j]:
				print(-1)
				sys.exit()
		else:
			data[i][j] = a[i][j]
			ans += a[i][j]
print(ans // 2)


import sys
N = int(input())
E = [list(map(int, input().split())) for _ in range(N)]
inf = float('inf')
for i in range(N):
	E[i][i] = inf
for k in range(N):
	for i in range(N):
		if i == k:
			continue
		for j in range(N):
			if k == j or i == j:
				continue
			direct = E[i][j]
			detour = E[i][k] + E[k][j]
			if direct == inf or detour == inf:
				continue
			if direct > detour:
				print(-1)
				sys.exit()
			elif direct == detour:
				E[i][j] = inf
				E[j][i] = inf
answer = 0
for i in range(N):
	for j in range(N):
		if E[i][j] == inf:
			continue
		answer += E[i][j]
print(answer // 2)


import sys
inf = float('inf')
N = int(input())
d = [list(map(int, input().split())) for _ in range(N)]
for i in range(N):
	d[i][i] = 0
ans = 0
for a in range(N):
	for b in range(N):
		flag = True
		for i in range(N):
			if i == a or i == b:
				continue
			if d[a][i] + d[i][b] < d[a][b]:
				print(-1)
				sys.exit()
			if d[a][i] + d[i][b] == d[a][b]:
				flag = False
				break
		if flag:
			ans += d[a][b]
print(ans // 2)


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
	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]
			elif dis_two_node < C[i, j]:
				print(-1)
				return
	print(total_dis)
Restoring_Road_Network()


import copy
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
b = copy.deepcopy(a)
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])
for i in range(n):
	for j in range(n):
		if b[i][j] != a[i][j]:
			print(-1)
			exit()
ans = 0
for i in range(n):
	for j in range(i + 1, n):
		m = 10 ** 18
		for k in range(n):
			if i == j or j == k or k == i:
				continue
			m = min(m, b[i][k] + b[k][j])
		if m > b[i][j]:
			ans += b[i][j]
print(ans)


n = int(input())
d = []
for i in range(n):
	tmp = [int(j) for j in input().split()]
	d.append(tmp)
ans = [[0] * n for i in range(n)]
for i in range(n):
	for j in range(i + 1, n):
		ans[i][j] = d[i][j]
for i in range(n):
	for j in range(i + 1, n):
		for k in range(n):
			if i == k or j == k:
				continue
			if d[i][j] > d[i][k] + d[k][j]:
				print(-1)
				exit()
			elif d[i][j] == d[i][k] + d[k][j]:
				ans[i][j] = 0
res = 0
for i in range(n):
	res += sum(ans[i])
print(res)


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())
G = [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 G[i][k] + G[k][j] < G[i][j]:
				print(-1)
				exit()
Need = [[True] * N for i in range(N)]
for k in range(N):
	for i in range(N):
		for j in range(N):
			if i == k or j == k:
				continue
			if G[i][k] + G[k][j] == G[i][j]:
				Need[i][j] = False
ans = 0
for i in range(N):
	for j in range(N):
		if Need[i][j]:
			ans += G[i][j]
print(ans // 2)


from copy import deepcopy
INF = 10 ** 18
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
c = deepcopy(a)
for k in range(n):
	for i in range(n):
		for j in range(n):
			c[i][j] = min(c[i][j], c[i][k] + c[k][j])
for i in range(n):
	for j in range(n):
		if a[i][j] != c[i][j]:
			print(-1)
			exit()
ans = 0
for i in range(n):
	for j in range(n):
		for k in range(n):
			if k == j or k == i:
				continue
			if c[i][j] == c[i][k] + c[k][j]:
				break
		else:
			ans += c[i][j]
print(ans // 2)


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()


n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
total = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		flg = True
		for x in range(n):
			if x == i or x == j:
				continue
			if a[i][j] > a[i][x] + a[j][x]:
				print(-1)
				exit()
			elif a[i][j] == a[i][x] + a[j][x]:
				flg = False
				break
		if flg:
			total += a[i][j]
print(total)


import heapq
import sys
N = int(input())
r = [[1] * N for _ in range(N)]
g = [[] * N for _ in range(N)]
all = 0
for i in range(N):
	temp = list(map(int, input().split()))
	g[i] = temp
	all += sum(temp)
for k in range(N):
	for i in range(N):
		for j in range(N):
			if g[i][j] > g[i][k] + g[k][j]:
				print('-1')
				sys.exit()
			elif g[i][j] == g[i][k] + g[k][j] and i != j and (j != k) and (k != i):
				r[i][j] = 0
ans = 0
for i in range(N):
	for j in range(N):
		ans += g[i][j] * r[i][j]
ans = ans // 2
print(ans)


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

def calc(N, A):
	r = 0
	if N == 1:
		return 0
	if N == 2:
		return A[0][1]
	for i in range(0, N):
		for j in range(i + 1, N):
			a = A[i][j]
			d = min((A[i][k] + A[k][j] for k in range(0, N) if k != i and k != j))
			if a > d:
				return -1
			if a < d:
				r += a
	return r
print(calc(N, A))


n = int(input())
dis = [list(map(int, input().split())) for _ in range(n)]
c = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
	for j in range(n):
		c[i][j] = min((dis[i][k] + dis[k][j] for k in range(n)))
for i in range(n):
	for j in range(n):
		if c[i][j] != dis[i][j]:
			print(-1)
			exit()
for i in range(n):
	for j in range(n):
		for k in range(n):
			if i == k or j == k:
				continue
			if dis[i][j] == dis[i][k] + dis[k][j]:
				c[i][j] = 0
print(sum((sum(c[i]) for i in range(n))) // 2)


import heapq
N = int(input())
A = [[] for i in range(N)]
Q = []
for i in range(N):
	A[i] = [int(x) for x in input().split()]
	for j in range(i + 1, N):
		heapq.heappush(Q, [A[i][j], i, j])
G = [[10 ** 9 + 1 for j in range(N)] for i in range(N)]
for i in range(N):
	G[i][i] = 0
cnt = 0
while Q:
	[d, s, t] = heapq.heappop(Q)
	add = True
	for k in range(N):
		if d > G[s][k] + G[k][t]:
			break
		if d == G[s][k] + G[k][t]:
			add = False
	else:
		G[s][t] = d
		G[t][s] = d
		cnt += d if add else 0
		continue
	print(-1)
	break
else:
	print(cnt)


N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
r = 0
for (i, aa) in enumerate(A):
	for (j, a) in enumerate(aa[i + 1:]):
		f = 1
		j += i + 1
		for k in range(N):
			if k == i or k == j:
				continue
			if a > A[i][k] + A[k][j]:
				f = r = -1
				break
			if a == A[i][k] + A[k][j]:
				f = 0
				break
		if f == 1:
			r += a
		elif f == -1:
			break
	if r < 0:
		break
print(r)


n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
B = [[1] * n for _ in range(n)]
for k in range(n):
	for i in range(n):
		for j in range(n):
			if k != i and k != j:
				if A[i][j] > A[i][k] + A[k][j]:
					print(-1)
					exit()
				elif 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):
		if B[i][j]:
			ans += A[i][j]
print(ans)


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 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))


N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
ans = 0
for i in range(N):
	for j in range(i + 1, N):
		ok = True
		for k in range(N):
			if i == k or j == k:
				continue
			if A[i][j] > A[i][k] + A[k][j]:
				print(-1)
				exit(0)
			elif A[i][j] == A[i][k] + A[k][j]:
				ok = False
		if ok:
			ans += A[i][j]
print(ans)


import sys

def main():
	N = int(input())
	A = [list(map(int, input().split())) for i in range(N)]
	ans = 0
	for i in range(N):
		for j in range(i + 1, N):
			dij = A[i][j]
			res = True
			for k in range(N):
				if k in [i, j]:
					continue
				dikj = A[i][k] + A[k][j]
				if dij > dikj:
					print(-1)
					sys.exit()
				elif dij == dikj:
					res = False
			if res:
				ans += dij
	print(ans)
main()


N = int(input())
A = [list(map(int, input().split())) for i in range(N)]
flag = True
Sum = 0
for i in range(N - 1):
	for j in range(i + 1, N):
		f = True
		for k in range(N):
			if k == i or k == j:
				continue
			if A[i][k] + A[k][j] < A[i][j]:
				flag = False
			elif A[i][k] + A[k][j] == A[i][j]:
				f = False
		if f:
			Sum += A[i][j]
if flag:
	print(Sum)
else:
	print(-1)


N = int(input())
A = [[] for i in range(N)]
for i in range(N):
	a = list(map(int, input().split()))
	A[i] = a
num = 0
for i in range(N):
	for j in range(i + 1, N):
		flag = True
		for k in range(N):
			if i == k 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 = False
		if flag:
			num += A[i][j]
print(num)


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

def Warshall_Floyd(edges, N):
	ans = 0
	for j in range(N):
		for i in range(N):
			flag = 0
			for k in range(N):
				if edges[i][j] > edges[i][k] + edges[k][j]:
					print(-1)
					exit()
				if edges[i][k] + edges[k][j] == edges[i][j] and i != k and (k != j):
					flag = 1
			if flag == 0:
				ans += edges[i][j]
	return (edges, ans)
(x, ans) = Warshall_Floyd(a, n)
print(ans // 2)


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()


N = int(input())
A = [[int(i) for i in input().split()] for _ in range(N)]
roads = [[True] * N for _ 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[j][k]:
				print(-1)
				exit()
			if i == j:
				roads[i][j] = False
			if i != k and j != k and (A[i][j] == A[i][k] + A[j][k]):
				roads[i][j] = False
ans = 0
for i in range(N):
	for j in range(i + 1, N):
		if roads[i][j] is True:
			ans += A[i][j]
print(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)


n = int(input())
a = [list(map(int, input().split())) for _ in [0] * 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()
ans = 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:
			ans += 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()


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()


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
n = int(input())
a = []
for _ in range(n):
	A = list(map(int, input().split()))
	a.append(A)
b = [[a[i][j] for j in range(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)
				sys.exit()
			if i != k and j != k and (a[i][k] + a[k][j] == a[i][j]):
				b[i][j] = 0
ans = 0
for i in range(n):
	ans += sum(b[i])
print(ans // 2)