Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import permutations, combinations

N=input()
d=[ [ float("inf") for j in range(N+1) ] for i in range(N+1) ] 

hen=[ [ 0 for j in range(N+1) ] for i in range(N+1) ] 
ans=0
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	d[i][i]=0
	for j in range(i+1,N):
		lengh=L[j]
		d[i+1][j+1]=lengh
		d[j+1][i+1]=lengh
		hen[i+1][j+1]=lengh
		ans+=lengh

d[N][N]=0

P=list( permutations(range(1,N+1),3) )

for i,j,k in P:
	a=d[i][j]
	b=d[j][k]
	c=d[i][k]	
	if a+b<c:
		print -1
		quit()
	if a+b==c and hen[i][k]!=0:
		ans-=c
		hen[i][k]=0
		hen[k][i]=0

print ans


Fixed submission:
import numpy as np
N = input()
A = [np.array(map(int,raw_input().split()), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
#print A


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop
from collections import defaultdict

N=input()
nl=[ [ ] for i in range(N+1) ] 

hq=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	for j in range(i+1,N):
		heappush( hq, (L[j],i+1,j+1) )


ans=0
for n in range(N-1):
	cost,x,y=heappop( hq )
	nl[x].append( (cost,y) )
	nl[y].append( (cost,x) )
	ans+=cost



def dij(start,end):
	#d=[ float("inf")  for i in range(N+1) ] 
	d=defaultdict(lambda: float("inf")) 
	d[start]=0
	q=[]
	heappush( q, start )	#u: chouten
	while q:
		fro=heappop(q)
		for cost, to in nl[fro]:
			alt=d[fro]+cost
			if d[to]>alt:
				d[to]=alt
				heappush(q,to)
	return d[end]

while hq:
	input_cost,x,y=heappop( hq )
	cost=dij(x,y)
	if cost < input_cost:
		print -1
		quit()
	elif input_cost<cost:
		nl[x].append( (input_cost,y) )
		nl[y].append( (input_cost,x) )
		ans+=input_cost

print ans

Fixed submission:
import numpy as np
N = input()
A = [np.array(map(int,raw_input().split()), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
#print A


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop
from collections import defaultdict

N=input()
nl=[ [ float("inf") for j in range(N+1) ] for i in range(N+1) ] 

hq=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	for j in range(i+1,N):
		heappush( hq, (L[j],i+1,j+1) )


ans=0
for n in range(N-1):
	cost,x,y,=heappop( hq )
	nl[x][y]=cost
	nl[y][x]=cost
	ans+=cost

def dij(start,end):
	d=defaultdict(lambda: float("inf")) 
	d[start]=0
	q=[]
	heappush( q, start )	#u: chouten

	while q:
		fro=heappop(q)
		for to in range(1,N+1):
			if nl[fro][to]==float("inf"): continue
			alt=d[fro]+nl[fro][to]
			if d[to]>alt:
				d[to]=alt
				heappush(q,to)
	return d[end]


while hq:
	cost,x,y=heappop( hq )
	d=dij(x,y)

	if d<cost:
		print -1
		quit()
	elif cost<d:
		ans+=cost
	nl[x][y]=cost
	nl[y][x]=cost


print ans


Fixed submission:
import numpy as np
N = input()
A = [np.array(map(int,raw_input().split()), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
#print A


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop
from collections import defaultdict

N=input()
nl=[ [ float("inf") for j in range(N+1) ] for i in range(N+1) ] 

hq=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	for j in range(i+1,N):
		heappush( hq, (L[j],i+1,j+1) )


ans=0
for n in range(N-1):
	cost,x,y,=heappop( hq )
	nl[x][y]=cost
	nl[y][x]=cost
	ans+=cost

def dij(start,end):
	d=defaultdict(lambda: float("inf")) 
	d[start]=0
	q=[]
	heappush( q, start )	#u: chouten

	while q:
		fro=heappop(q)
		for to in range(1,N+1):
			alt=d[fro]+nl[fro][to]
			if d[to]>alt:
				d[to]=alt
				heappush(q,to)
	return d[end]


while hq:
	cost,x,y,=heappop( hq )
	d=dij(x,y)

	if d<cost:
		print -1
		quit()
	elif cost<d:
		ans+=cost
	nl[x][y]=cost
	nl[y][x]=cost


print ans


Fixed submission:
import numpy as np
N = input()
A = [np.array(map(int,raw_input().split()), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
#print A


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop

N=input()
nl=[ [ float("inf") for j in range(N+1) ] for i in range(N+1) ] 

hq=[]
for i in range(N):
	L=map(int, sys.stdin.readline().split())
	for j in range(i+1,N):
		heappush( hq, (L[j],i+1,j+1) )


ans=0
for n in range(N-1):
	cost,x,y,=heappop( hq )
	nl[x][y]=cost
	nl[y][x]=cost
	ans+=cost

def dij(start,end):
	d=[ float("inf") for _ in range(N+1)]
	d[start]=0
	q=[]
	heappush( q, start )	#u: chouten

	while q:
		fro=heappop(q)
		for to in range(1,N+1):
			alt=d[fro]+nl[fro][to]
			if d[to]>alt:
				d[to]=alt
				heappush(q,to)
	return d[end]


while hq:
	cost,x,y,=heappop( hq )
	d=dij(x,y)

	if d<cost:
		print -1
		quit()
	elif cost<d:
		ans+=cost
	nl[x][y]=cost
	nl[y][x]=cost


print ans


Fixed submission:
import numpy as np
N = input()
A = [np.array(map(int,raw_input().split()), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
#print A


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

Buggy python submission (verdict: Time Limit Exceeded):
N=input()
cost={}

org=[[float("inf") for i in range(N)] for _ in range(N)]
for i in range(N):
	A=map(int, raw_input().split())
	for j in range(N):
		org[i][j]=A[j]
		if j>i:
			cost[(i,j)]=A[j]


for param in range(-1,len(cost)-N+1):

	cost_sel=sorted(cost.items(), key=lambda x: x[1])[:N+param]

	#Initialize
	dp=[[float("inf") for i in range(N)] for _ in range(N)]
	for i in range(N): dp[i][i]=0

	for i,j in cost_sel:
		dp[i[0]][i[1]]=j
		dp[i[1]][i[0]]=j

	#Warshall-Floyd
	for k in range(N):
		for x in range(N):
			for y in range(N):
				dp[x][y]=min(dp[x][y], dp[x][k]+dp[k][y])

	#print dp
	if org==dp:
		print sum( [x[1] for x in cost_sel] )
		quit()
else:
	print -1
		

Fixed submission:
import numpy as np
N = input()
A = [np.array(map(int,raw_input().split()), dtype=np.int64) for _ in [0]*N]
inf = 10**10
for i in range(N):
    A[i][i] = inf
#print A


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