Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq,copy

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def warshall_floyd(d):
    """Warshall Floyd method"""

    n = len(d)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

def solve(f):
    n = f.read_int()
    a = [f.read_int_list() for _ in xrange(n)]

    aorg = copy.deepcopy(a)
    warshall_floyd(a)

    for i in xrange(n):
        for j in xrange(n):
            if aorg[i][j] != a[i][j]: return -1

    ans = 0
    for i in xrange(n):
        for j in xrange(n):
            if i == j: continue
            for k in xrange(n):
                if i == k or j == k: continue
                if a[i][j] == a[i][k] + a[k][j]: break
            else:
                ans += a[i][j]

    return ans/2


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)


Fixed submission:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq,copy

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

def warshall_floyd(d):
    """Warshall Floyd method"""

    n = len(d)
    for i in range(n):
        for j in range(n):
            for k in range(n):
                if d[i][j] > d[i][k] + d[k][j]:
                    d[i][j] = d[i][k] + d[k][j]

def solve(f):
    n = f.read_int()
    a = [f.read_int_list() for _ in xrange(n)]

    aorg = copy.deepcopy(a)
    warshall_floyd(a)

    for i in xrange(n):
        for j in xrange(n):
            if aorg[i][j] != a[i][j]: return -1

    ans = 0
    for i in xrange(n):
        for j in xrange(n):
            if i == j: continue
            for k in xrange(n):
                if i == k or j == k: continue
                if a[i][j] == a[i][k] + a[k][j]: break
            else:
                ans += a[i][j]

    return ans/2


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)