Problem:
 Score : 500 points    Problem Statement 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 1 3
0 1 3
1 0 2
3 2 0      Sample Output 1 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.        Sample Input 2 3
0 1 3
1 0 1
3 1 0      Sample Output 2 -1  As there is a path of length 1 from City 1 to City 2 and City 2 to City 3 , there is a path of length 2 from City 1 to City 3 .
However, according to the table, the shortest distance between City 1 and City 3 must be 3 .  Thus, we conclude that there exists no network that satisfies the condition.       Sample Input 3 5
0 21 18 11 28
21 0 13 10 26
18 13 0 23 13
11 10 23 0 17
28 26 13 17 0      Sample Output 3 82       Sample Input 4 3
0 1000000000 1000000000
1000000000 0 1000000000
1000000000 1000000000 0      Sample Output 4 3000000000

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
from copy import deepcopy
import sys
input = sys.stdin.readline


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


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

Solution (Python):
def JOI14_B():
    N = I()
    A = [I()for _ in range(N)]
    A.extend(A)
    dp = [[0]*(N*2+1) for _ in range(N*2+1)]

    for j in range(N):
        for i in range(N*2-j):
            if (N-j)%2==1:
                dp[i][i+j] = max(dp[i+1][i+j]+A[i],dp[i][i+j-1]+A[i+j])
            else:
                if A[i]>A[i+j]:
                    dp[i][i+j] = dp[i+1][i+j]
                else:
                    dp[i][i+j] = dp[i][i+j-1]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][i+N-1])
    print(ans)
    
    return

def square869120Contest1_G():
    def held_karp(dists,TL):
        
        """
        Implementation of Held-Karp, an algorithm that solves the Traveling
        Salesman Problem using dynamic programming with memoization.
        Parameters:
            dists: distance matrix
        Returns:
            A tuple, (cost, path).
        """
        n = len(dists)

        
        
        
        C = {}
        dp = defaultdict(int)

        
        for k in range(1, n):
            C[(1 << k, k)] = (dists[0][k], 0)
            dp[(1 << k, k)] = 1

        
        
        for subset_size in range(2, n):
            for subset in itertools.combinations(range(1, n), subset_size):
                
                bits = 0
                for bit in subset:
                    bits |= 1 << bit
                shortest_length = inf
                
                for k in subset:
                    prev = bits & ~(1 << k)

                    res = []
                    for m in subset:
                        if not (prev, m) in C:
                            continue
                        if m == 0 or m == k:
                            continue
                        if C[(prev, m)][0] + dists[m][k]>TL[m][k]:
                            continue
                        res.append((C[(prev, m)][0] + dists[m][k], m))
                        if shortest_length>C[(prev, m)][0] + dists[m][k]:
                            shortest_length = C[(prev, m)][0] + dists[m][k]
                    if not res:
                        continue
                    C[(bits, k)] = min(res)
                    for d,m in res:
                        if shortest_length!=d:
                            continue
                        dp[(bits, k)] += dp[(prev,m)]

        
        bits = (2 ** n - 1) - 1

        
        res = []
        shortest_length = inf
        for k in range(1, n):
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            res.append((C[(bits, k)][0] + dists[k][0], k))
            if shortest_length > C[(bits, k)][0] + dists[k][0]:
                shortest_length = C[(bits, k)][0] + dists[k][0]
        if not res:
            return False
        opt, parent = min(res)
        way = 0
        for d, k in res:
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            if shortest_length < d:
                continue
            way += dp[(bits,k)]

        
        path = []
        for i in range(n - 1):
            path.append(parent)
            new_bits = bits & ~(1 << parent)
            _, parent = C[(bits, parent)]
            bits = new_bits

        
        path.append(0)

        return shortest_length, list(reversed(path)), way

    N, M = LI()
    dist = [[inf]*N for _ in range(N)]
    TL = [[0]*N for _ in range(N)]
    for _ in range(M):
        s, t, d, time = LI()
        s -= 1; t -= 1
        dist[s][t] = dist[t][s] = d
        TL[s][t] = TL[t][s] = time
    ans = held_karp(dist,TL)
    if (not ans) or ans[2]==0:
        print("IMPOSSIBLE")
        return
    print(ans[0],ans[2])
    return

def JOI13_D():
    def solve(yday,leader,next):
        a = [0]*3
        for i in range(3):
            if next&(1<<i)==(1<<i):
                a[i] = 1
        rep = 0
        if a[leader]==0:
            return rep
        for i in range(3):
            if yday&(1<<i)==(1<<i):
                if a[i]==1:
                    rep = 1
        return rep
    N = I()
    S = SI()
    member = {"J":0,"O":1,"I":2}
    dp = [[0]*8 for _ in range(N+1)]
    dp[0][1] = 1
    for i in range(N):
        leader = member[S[i]]
        for j in range(8):
            for k in range(8):
                dp[i+1][j] += (dp[i][k]*solve(k,leader,j))
    ans = sum(dp[-1])%10007
    
    print(ans)
    return

def JOI16_D():
    N, M = LI()
    A = [(I()-1)for _ in range(N)]
    imos = [[0] * (N + 1) for _ in range(M)]
    for i in range(M):
        for j in range(N):
            imos[i][j + 1] += imos[i][j] + (A[j] != i)
    loop = 2**M
    dp = [inf]*loop
    dp[0] = 0
    cnt = Counter(A)
    L = [0]*loop
    
    for i in range(loop):
        for j in range(M):
            if i&(1<<j)==(1<<j):
                continue
            next = i|(1<<j)
            if L[next]==0:
                L[next] = L[i]+cnt[j]
            cur = imos[j][L[next]] - imos[j][L[i]]
            if dp[next]>dp[i] + cur:
                dp[next] = dp[i] + cur
    ans = dp[-1]
    
    print(ans)
    return

def ABC6_D():
    N = I()
    C = [I() for _ in range(N)]
    LIS = [C[0]]
    for i in range(N):
        if C[i] > LIS[-1]:
            LIS.append(C[i])
        else:
            LIS[bisect.bisect_left(LIS, C[i])] = C[i]
    print(N - len(LIS))
    return

def ABC134_E():
    N = I()
    A = [I()for _ in range(N)]
    que = deque()
    que.append(A[0])
    L = 1
    for i in range(1,N):
        cur = bisect.bisect_left(que,A[i])
        
        if cur==0:
            que.appendleft(A[i])
            L += 1
        else:
            que[cur-1] = A[i]

    
    ans = len(que)
    print(ans)

    return

def JOI7_F():
    def dijkstra_2(edge_adj, node, start):
        
        
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    V = [[inf]*N for _ in range(N)]
    ans = []
    for _ in range(K):
        A = LI()
        s = A[1]-1
        t = A[2]-1
        if A[0]==1:
            if V[s][t] <= A[3]:
                continue
            V[s][t] = A[3]
            V[t][s] = A[3]
        else:
            dist = dijkstra_2(V,N,s)
            ans.append(dist[t])
    for v in ans:
        if v==inf:
            print(-1)
            continue
        print(v)
    return

def JOI15_E():
    def bfs(n, E, fordfs):
        
        W = [inf] * n
        
        que = deque()
        for e in E:
            e -=1
            W[e] = 0
            que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] > nowW + 1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    class Dijkstra(object):
        """
        construct: O(ElogV)
        """

        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, M, K, S = LI()
    P, Q = LI()
    C = [I()for _ in range(K)]
    V = [[]for _ in range(N)]
    for _ in range(M):
        s, t = LI()
        s -= 1
        t -= 1
        V[s].append(t)
        V[t].append(s)
    L = bfs(N,C,V)
    
    cost = [[]for _ in range(N)]
    for i in range(N):
        for v in V[i]:
            if L[v]==0:
                continue
            elif L[v]<=S:
                cost[i].append((v,Q))
            else:
                cost[i].append((v,P))
    di = Dijkstra(cost)
    ans = di.dist
    
    if L[-1]<=S:
        print(ans[N-1]-Q)
    else:
        print(ans[N-1]-P)
    return

def JOI13_E():
    def bfs(n, e, fordfs):
        
        W = [inf] * n
        
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == inf:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    def dijkstra_2(edge_adj, node, start):
        
        
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    C = [[]for _ in range(N)]
    V = [[]for _ in range(N)]
    for i in range(N):
        C[i] = LI()
    for i in range(K):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    costV = [[inf]*N for _ in range(N)]
    for i in range(N):
        L = bfs(N,i,V)
        c = C[i][0]; l = C[i][1]
        for j in range(N):
            if i==j:
                continue
            if L[j]<=l:
                costV[i][j] = c
    dist = dijkstra_2(costV,N,0)
    ans = dist[N-1]
    
    print(ans)
    return

def ABC12_D():
    def warshall_floyd(n, d):
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    N, M = LI()
    V = [[inf]*N for _ in range(N)]
    for i in range(N):
        V[i][i] = 0
    for _ in range(M):
        a, b, t = LI()
        a -= 1
        b -= 1
        V[a][b] = t
        V[b][a] = t
    L = warshall_floyd(N,V)
    
    ans = inf
    for i in range(N):
        cur = max(L[i])
        ans = min(ans,cur)
    print(ans)
    return

def ABC79_D():
    def warshall_floyd(n, d):
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    H, W = LI()
    C = [LI()for _ in range(10)]
    A = [LI()for _ in range(H)]
    L = warshall_floyd(10,C)
    
    ans = 0
    for a in A:
        for i in a:
            if i>=0:
                ans += L[i][1]
    print(ans)
    return

def JOIgassyuku10_3():
    N, M, K = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b, c = LI()
        a -= 1
        b -= 1
        V[a].append((b,c))
        V[b].append((a,c))


    return

def ABC74_D():
    def warshall_floyd(n, d):
        
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    N = I()
    A = [LI() for _ in range(N)]
    dist = warshall_floyd(N,copy.deepcopy(A))
    shortest_path = 0
    for i in range(N):
        for j in range(N):
            if i==j:
                continue
            if dist[i][j]<A[i][j]:
                print(-1)
                return
            if dist[i][j]>A[i][j]:
                continue
            flag = True
            for k in range(N):
                if i==k or j==k:
                    continue
                judge = (dist[i][k]+dist[k][j])-dist[i][j]
                if judge==0:
                    flag = False
            if flag:
                shortest_path += A[i][j]
    ans = shortest_path//2
    print(ans)
    return



def square869120Contest1_E():
    N, Q = LI()
    A = LI()
    C = LI()
    C.append(1)
    L = [0]*N
    for i in range(1,N):
        L[i] = pow(A[i-1],A[i],mod) + L[i-1]
    
    ans = 0
    now = 0
    for i in range(Q+1):
        next = C[i]-1
        cur = abs(L[next]-L[now])
        ans += cur
        ans %= mod
        now = next
        
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque

import gc
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    ABC74_D()
"""

"""

Solution (Python):
import copy

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

Check = copy.deepcopy(A)

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

Graph_exist = True
for i in range(n):
    for j in range(n):
        if A[i][j] != Check[i][j]:
            Graph_exist = False

Road_exist = [[True for _ in range(n)] for _ in range(n)]
for i in range(n):
    Road_exist[i][i] = False

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j or i==k or j==k:
                continue
            if A[i][j] == (A[i][k] + A[k][j]):
                Road_exist[i][j] = False

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if Road_exist[i][j] == True:
            ans += A[i][j]

if Graph_exist == False:
    ans = -1
print(ans)

Solution (Python):
N = int(input())
A = [list(map(int, input().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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]

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

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

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

Solution (Python):
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)

Solution (Python):

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()
"""
a[i][j]が、i,kを除く全てのkについて
a[i][j]<a[i][k]+a[k][j]なら
a[i][j]は最短経路となる。
"""
ans=0
for i in range(n):
    for j in range(i+1,n):
        
        flg=True
        for k in range(n):
            if i==k or j==k:
                continue
            if a[i][j]==a[i][k]+a[k][j]:
                flg=False
                break
        if flg:
            ans+=a[i][j]
print(ans)

Solution (Python):

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


"""
Aの要素について、全てに辺が貼られているような状態を考えて、
あるA[i][j]が、i,kを除く全てのkについて A[i][j] < A[i][k] + A[k][j]であれば、
A[i][j]は最短の経路であるといえる

"""
ans = 0
for i in range(N):
    for j in range(i+1,N):


        flag = True 
        for k in range(N):
            if i == k or j == k:
                continue
            
            
            if A[i][j] == A[i][k] + A[k][j]:
                flag = False
                break
        if flag:
            ans += A[i][j]

        
print(ans)

Solution (Python):
from copy import deepcopy

def warshall_floyd(n,a):
    d = deepcopy(a)
    is_via = [[False] * n for _ in range(n)]
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                
                if (d[i][k] != 0 and d[k][j] != 0) and (d[i][j] == d[i][k] + d[k][j]):
                    is_via[i][j] = True
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])
    flag = a == d
    return flag, is_via

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

flag, is_via = warshall_floyd(N,A)

if not flag:
    print(-1)
    exit()

ans = 0
for i in range(N):
    for j in range(i,N):
        if is_via[i][j]:
            continue
        ans += A[i][j]

print(ans)

Solution (Python):
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)

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    inf=10*20
    N=I()
    A=[[]for _ in range(N)]
    A2=[[1]*N for _ in range(N)]
    ans=0
    for i in range(N):
        A[i]=LI()
        ans+=sum(A[i])
        
    


        
    def warshall_floyd(d):
        
        for k in range(N):
            for i in range(N):
                if k==i:
                    continue
                for j in range(N):
                    if j==i or j==k:
                        continue
                    dd=d[i][k] + d[k][j]
                    
                    
                    if dd==d[i][j]:
                        A2[i][j]=0
                    elif dd<d[i][j]:
                        return -1
        return 1
    
    if warshall_floyd(A)==-1:
        ans=-2
    else:
        ans=0
        for i in range(N):
            for j in range(N):
                ans+=A[i][j]*A2[i][j]
        
        
    print(ans//2)
        
    

main()

Solution (Python):
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = []
for i in range(n):
    a.append(inl())
c = [[True]*n for i in range(n)]
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if a[i][j] > a[i][k]+a[k][j] or \
               a[i][k] > a[i][j]+a[j][k] or \
               a[k][j] > a[k][i]+a[i][j]:
                print(-1)
                exit()
            elif a[i][j] == a[i][k]+a[k][j]:
                c[i][j] = False
            elif a[i][k] == a[i][j]+a[j][k]:
                c[i][k] = False
            elif a[k][j] == a[k][i]+a[i][j]:
                c[j][k] = False
sm = 0
for i in range(n-1):
    for j in range(i+1,n):
        if c[i][j]:
            sm += a[i][j]
print(sm)

Solution (Python):
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)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from heapq import heappush, heappop

    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):
            if a[i][j] != min(a[i][k] + a[k][j] for k in range(n)):
                print(-1)
                return

    h = []
    for r, row in enumerate(a):
        for c, cell in enumerate(row):
            if r == c: break
            heappush(h, (cell, r, c))  

    pathes = []
    while h:
        dist, r, c = heappop(h)

        is_path = True
        for k in range(n):
            if k == r or k == c: continue
            if dist >= a[r][k] + a[k][c]:
                is_path = False
                break

        if is_path:
            pathes.append(dist)

    print(sum(pathes))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())

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

Solution (Python):
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)

Solution (Python):
n = int(input())
a = []
ans = 0
for i in range(n):
    k = list(map(int, input().split()))
    a.append(k)
flag = [[True for i in range(n)] for j in range(n)]
for i in range(n):
    for j in range(n):
        for k in range(n):
            if a[j][i] + a[i][k] < a[j][k]:
                print(-1)
                exit()
            elif a[j][i] + a[i][k] == a[j][k] and j != i and i != k:
                flag[j][k] = flag[k][j] = False
for i in range(n):
    for j in range(n):
        if flag[i][j]:
            ans += a[i][j]
print(ans//2)

Solution (Python):
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)