The problem is to find the shortest distances between every pair of vertices in a given edge-weighted directed graph. The graph is represented as an adjacency matrix of size n*n. Matrix[i][j] denotes the weight of the edge from i to j. If Matrix[i][j]=-1, it means there is no edge from i to j.
Do it in-place.
Example 1:
Input: matrix = {{0,25},{-1,0}}
Output: {{0,25},{-1,0}}
Explanation: The shortest distance between
every pair is already given(if it exists).
Example 2:
Input: matrix = {{0,1,43},{1,0,6},{-1,-1,0}}
Output: {{0,1,7},{1,0,6},{-1,-1,0}}
Explanation: We can reach 2 from 0 as 0->1->2
and the cost will be 1+6=7 which is less than 
43.
Your Task:
You don't need to read, return or print anything. Your task is to complete the function shortest_distance() which takes the matrix as input parameter and modifies the distances for every pair in-place.
Expected Time Complexity: O(n^{3})
Expected Space Complexity: O(1)
Constraints:
1 <= n <= 100
-1 <= matrix[ i ][ j ] <= 1000

Difficulty: MEDIUM
Tags: Dynamic programming

Graph algorithms

Data structures
Skill types: Dynamic programming

Data structures
Expected Time Complexity: O(n^{3})
Expected Auxiliary Space: O(1)

Starter code:
#User function template for Python



class Solution:

	def shortest_distance(self, matrix):

		#Code here

Solutions:
class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == -1:
					matrix[i][j] = float('inf')
				if i == j:
					matrix[i][j] = 0
		for k in range(n):
			for i in range(n):
				for j in range(m):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == float('inf'):
					matrix[i][j] = -1


class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = 1000000007
				if i == j:
					matrix[i][j] = 0
		for via in range(n):
			for i in range(n):
				for j in range(n):
					matrix[i][j] = min(matrix[i][via] + matrix[via][j], matrix[i][j])
		for i in range(n):
			for j in range(n):
				if matrix[i][j] >= 1000000007:
					matrix[i][j] = -1


class Solution:

	def shortest_distance(self, matrix):
		return floyd_warshall(matrix)

def change_to_inf(G):
	for i in range(len(G)):
		for j in range(len(G)):
			if G[i][j] == -1:
				G[i][j] = float('inf')
	return G

def back_to_inf(G):
	for i in range(len(G)):
		for j in range(len(G)):
			if G[i][j] == float('inf'):
				G[i][j] = -1
	return G

def floyd_warshall(G):
	n = len(G)
	G = change_to_inf(G)
	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]:
					G[i][j] = G[i][k] + G[k][j]
	return back_to_inf(G)


class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for k in range(n):
			for i in range(n):
				for j in range(n):
					if matrix[i][k] < 0 or matrix[k][j] < 0:
						continue
					if matrix[i][j] == -1:
						matrix[i][j] = matrix[i][k] + matrix[k][j]
					elif matrix[i][j] > matrix[i][k] + matrix[k][j]:
						matrix[i][j] = matrix[i][k] + matrix[k][j]


class Solution:

	def shortest_distance(self, matrix):
		rows = len(matrix)
		cols = len(matrix[0])
		for row in range(rows):
			for col in range(cols):
				if matrix[row][col] == -1:
					matrix[row][col] = 1001
		for k in range(rows):
			for src in range(rows):
				for dest in range(rows):
					matrix[src][dest] = min(matrix[src][dest], matrix[src][k] + matrix[k][dest])
		for row in range(rows):
			for col in range(cols):
				if matrix[row][col] == 1001:
					matrix[row][col] = -1


class Solution:

	def shortest_distance(self, matrix):
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if i == j:
					matrix[i][j] = 0
					continue
				if matrix[i][j] == -1:
					matrix[i][j] = 10 ** 9
		for k in range(len(matrix)):
			for i in range(len(matrix)):
				for j in range(len(matrix)):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == 10 ** 9:
					matrix[i][j] = -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for k in range(n):
			for i in range(n):
				for j in range(n):
					if matrix[i][k] != -1 and matrix[k][j] != -1:
						if matrix[i][j] == -1 or matrix[i][k] + matrix[k][j] < matrix[i][j]:
							matrix[i][j] = matrix[i][k] + matrix[k][j]
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = int(1000000000.0)
				if i == j:
					matrix[i][j] = 0
		for k in range(n):
			for i in range(n):
				for j in range(n):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == int(1000000000.0):
					matrix[i][j] = -1


class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for i in range(n):
			for j in range(n):
				for k in range(n):
					if matrix[j][k] == -1:
						if matrix[j][i] != -1 and matrix[i][k] != -1:
							matrix[j][k] = matrix[j][i] + matrix[i][k]
					elif matrix[j][i] != -1 and matrix[i][k] != -1:
						matrix[j][k] = min(matrix[j][k], matrix[j][i] + matrix[i][k])


class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = 1001
		for k in range(n):
			for src in range(n):
				for des in range(n):
					matrix[src][des] = min(matrix[src][des], matrix[src][k] + matrix[k][des])
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == 1001:
					matrix[i][j] = -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for row in range(0, n):
			for col in range(0, n):
				if matrix[row][col] == -1:
					matrix[row][col] = 10001
		for k in range(0, n):
			for src in range(0, n):
				for dest in range(0, n):
					matrix[src][dest] = min(matrix[src][dest], matrix[src][k] + matrix[k][dest])
		for row in range(0, n):
			for col in range(0, n):
				if matrix[row][col] == 10001:
					matrix[row][col] = -1


class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for row in range(n):
			for col in range(n):
				if matrix[row][col] == -1:
					matrix[row][col] = 1001
		for via in range(n):
			for src in range(n):
				for des in range(n):
					matrix[src][des] = min(matrix[src][des], matrix[src][via] + matrix[via][des])
		for row in range(n):
			for col in range(n):
				if matrix[row][col] == 1001:
					matrix[row][col] = -1


class Solution:

	def shortest_distance(self, matrix):
		row = len(matrix)
		col = len(matrix[0])
		for r in range(row):
			for c in range(col):
				if matrix[r][c] == -1:
					matrix[r][c] = 10000
		for k in range(row):
			for src in range(row):
				for dest in range(col):
					matrix[src][dest] = min(matrix[src][dest], matrix[src][k] + matrix[k][dest])
		for r in range(row):
			for c in range(col):
				if matrix[r][c] == 10000:
					matrix[r][c] = -1


import sys

class Solution:

	def shortest_distance(self, matrix):
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = sys.maxsize
		for via in range(n):
			for i in range(n):
				for j in range(n):
					matrix[i][j] = min(matrix[i][j], matrix[i][via] + matrix[via][j])
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == sys.maxsize:
					matrix[i][j] = -1


import sys

class Solution:

	def shortest_distance(self, matrix):
		m = len(matrix)
		n = len(matrix[0])
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = sys.maxsize
				elif i == j:
					matrix[i][j] = 0
		for k in range(n):
			for i in range(n):
				for j in range(n):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == sys.maxsize:
					matrix[i][j] = -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = float('inf')
		for via in range(n):
			for i in range(n):
				for j in range(n):
					matrix[i][j] = min(matrix[i][j], matrix[i][via] + matrix[via][j])
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == float('inf'):
					matrix[i][j] = -1
		return matrix


from math import inf

class Solution:

	def shortest_distance(self, matrix):
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == -1:
					matrix[i][j] = inf
				elif i == j:
					matrix[i][j] = 0
		for k in range(len(matrix)):
			for i in range(len(matrix)):
				for j in range(len(matrix)):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == inf:
					matrix[i][j] = -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for x in range(n):
			for y in range(n):
				if matrix[x][y] == -1:
					matrix[x][y] = float('inf')
		for k in range(n):
			for i in range(n):
				for j in range(n):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for x in range(n):
			for y in range(n):
				if matrix[x][y] >= float('inf'):
					matrix[x][y] = -1
		return matrix


import math

class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = math.inf
		for k in range(n):
			for i in range(n):
				for j in range(n):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == math.inf:
					matrix[i][j] = -1


class Solution:

	def shortest_distance(self, matrix):
		V = len(matrix)
		for k in range(V):
			for u in range(V):
				if matrix[u][k] == -1:
					continue
				for v in range(V):
					if matrix[k][v] == -1:
						continue
					if matrix[u][v] == -1:
						matrix[u][v] = matrix[u][k] + matrix[k][v]
					elif matrix[u][k] + matrix[k][v] < matrix[u][v]:
						matrix[u][v] = matrix[u][k] + matrix[k][v]


class Solution:

	def shortest_distance(self, matrix):
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == -1:
					matrix[i][j] = int(100000000.0)
				if i == j:
					matrix[i][j] = 0
		for via in range(len(matrix)):
			for i in range(len(matrix)):
				for j in range(len(matrix[0])):
					matrix[i][j] = min(matrix[i][j], matrix[i][via] + matrix[via][j])
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if matrix[i][j] == int(100000000.0):
					matrix[i][j] = -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		V = len(matrix)
		for e in range(V):
			for i in range(V):
				for j in range(V):
					curr = matrix[i][j] if matrix[i][j] != -1 else float('inf')
					next = matrix[i][e] + matrix[e][j] if matrix[i][e] != -1 and matrix[e][j] != -1 else float('inf')
					matrix[i][j] = min(curr, next)
					matrix[i][j] = matrix[i][j] if matrix[i][j] != float('inf') else -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		m = len(matrix)
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = float('inf')
		for k in range(m):
			for i in range(m):
				for j in range(m):
					if matrix[i][k] == float('inf') or matrix[k][j] == float('inf'):
						continue
					else:
						matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for i in range(m):
			for j in range(n):
				if matrix[i][j] == float('inf'):
					matrix[i][j] = -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		ans = [[0 for _ in range(len(matrix[i]))] for i in range(len(matrix))]
		INF = float('inf')
		for i in range(len(matrix)):
			for j in range(len(matrix[i])):
				if matrix[i][j] != -1:
					ans[i][j] = matrix[i][j]
				else:
					ans[i][j] = INF
		for k in range(len(matrix)):
			for i in range(len(matrix)):
				for j in range(len(matrix[i])):
					if ans[i][k] < INF and ans[k][j] < INF and (ans[i][k] + ans[k][j] < INF):
						ans[i][j] = min(ans[i][k] + ans[k][j], ans[i][j])
		for i in range(len(matrix)):
			for j in range(len(matrix[i])):
				if matrix[i][j] != INF:
					matrix[i][j] = ans[i][j]
				else:
					matrix[i][j] = -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = 999999
		for k in range(n):
			for i in range(n):
				for j in range(n):
					if matrix[i][k] + matrix[k][j] < matrix[i][j]:
						matrix[i][j] = matrix[i][k] + matrix[k][j]
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == 999999:
					matrix[i][j] = -1


class Solution:

	def shortest_distance(self, cost):
		n = len(cost)
		for k in range(n):
			for i in range(n):
				for j in range(n):
					if i == j:
						continue
					if cost[i][k] != -1 and cost[k][j] != -1:
						if cost[i][j] == -1:
							cost[i][j] = cost[i][k] + cost[k][j]
						elif cost[i][j] > cost[i][k] + cost[k][j]:
							cost[i][j] = cost[i][k] + cost[k][j]
		return cost


from math import inf

class Solution:

	def shortest_distance(self, matrix):
		V = len(matrix)
		dists = matrix
		for k in range(V):
			for i in range(V):
				for j in range(V):
					if dists[i][k] == -1 or dists[k][j] == -1:
						continue
					dists[i][j] = min(dists[i][k] + dists[k][j], dists[i][j] if dists[i][j] != -1 else inf)
		return dists


class Solution:

	def shortest_distance(self, matrix):
		m = len(matrix)
		for i in range(m):
			for j in range(m):
				if matrix[i][j] == -1:
					matrix[i][j] = 100000000
		for k in range(m):
			for i in range(m):
				for j in range(m):
					if matrix[i][k] + matrix[k][j] < matrix[i][j]:
						matrix[i][j] = matrix[i][k] + matrix[k][j]
		for i in range(m):
			for j in range(m):
				if matrix[i][j] == 100000000:
					matrix[i][j] = -1
		return matrix


from math import inf
inf = float('inf')

class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for i in range(n):
			for j in range(n):
				if i == j:
					matrix[i][j] = 0
				elif matrix[i][j] == -1:
					matrix[i][j] = inf
		for via in range(n):
			for i in range(n):
				for j in range(n):
					matrix[i][j] = min(matrix[i][j], matrix[i][via] + matrix[via][j])
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == inf:
					matrix[i][j] = -1


class Solution:

	def shortest_distance(self, matrix):
		(n, m) = (len(matrix), len(matrix[0]))
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = 10000000000.0
				if i == j:
					matrix[i][j] = 0
		for via in range(n):
			for i in range(n):
				for j in range(n):
					matrix[i][j] = min(matrix[i][j], matrix[i][via] + matrix[via][j])
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == 10000000000.0:
					matrix[i][j] = -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		m = len(matrix[0])
		for i in range(n):
			for j in range(m):
				if matrix[i][j] == -1:
					matrix[i][j] = 10 ** 9
				if i == j:
					matrix[i][j] = 0
		for k in range(n):
			for i in range(n):
				for j in range(n):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == 10 ** 9:
					matrix[i][j] = -1


class Solution:

	def shortest_distance(self, matrix):
		for i in range(len(matrix)):
			for j in range(len(matrix[i])):
				if i == j:
					matrix[i][j] = 0
				elif matrix[i][j] == -1:
					matrix[i][j] = 10 ** 9
		for via in range(len(matrix)):
			for i in range(len(matrix)):
				for j in range(len(matrix[i])):
					matrix[i][j] = min(matrix[i][j], matrix[i][via] + matrix[via][j])
		for i in range(len(matrix)):
			for j in range(len(matrix[i])):
				if matrix[i][j] == 10 ** 9:
					matrix[i][j] = -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		v = len(matrix)
		for i in range(v):
			for j in range(v):
				if matrix[i][j] == -1:
					matrix[i][j] = float('inf')
		for k in range(v):
			for i in range(v):
				for j in range(v):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for i in range(v):
			if matrix[i][i] < 0:
				return '-ve cycle exist'
		for i in range(v):
			for j in range(v):
				if matrix[i][j] == float('inf'):
					matrix[i][j] = -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		v = len(matrix)
		for i in range(v):
			for j in range(v):
				if matrix[i][j] == -1:
					matrix[i][j] = float('inf')
		for k in range(v):
			for i in range(v):
				for j in range(v):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for i in range(v):
			for j in range(v):
				if matrix[i][j] == float('inf'):
					matrix[i][j] = -1
		return matrix


class Solution:

	def helper(self, source, dest, visited):
		if source == dest:
			return 0
		if source in visited:
			return 10 ** 9
		visited.add(source)
		ans = self.matrix[source][dest]
		for i in range(len(self.matrix[0])):
			if self.matrix[source][i] != -1:
				ans = min(ans, self.matrix[source][i] + self.helper(i, dest, visited))
		self.matrix[source][dest] = ans
		return ans

	def shortest_distance(self, matrix):
		n = len(matrix)
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = 10 ** 9
		for k in range(n):
			for i in range(n):
				for j in range(n):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == 10 ** 9:
					matrix[i][j] = -1
		return matrix


from math import inf

class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		cost = matrix.copy()
		for i in range(n):
			for j in range(n):
				if cost[i][j] == -1:
					cost[i][j] = inf
		for via in range(n):
			for i in range(n):
				for j in range(n):
					if cost[i][j] > cost[i][via] + cost[via][j]:
						cost[i][j] = cost[i][via] + cost[via][j]
		for i in range(n):
			for j in range(n):
				if cost[i][j] == inf:
					cost[i][j] = -1
		return cost


import math

class Solution:

	def shortest_distance(self, matrix):
		N = len(matrix)
		for i in range(N):
			for j in range(N):
				if matrix[i][j] == -1:
					matrix[i][j] = 9999999
		for k in range(N):
			for i in range(N):
				for j in range(N):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for i in range(N):
			for j in range(N):
				if matrix[i][j] == 9999999:
					matrix[i][j] = -1


INF = 99999

class Solution:

	def shortest_distance(self, D):
		n = len(D)
		for i in range(n):
			for j in range(n):
				if D[i][j] == -1:
					D[i][j] = INF
		for k in range(n):
			for i in range(n):
				for j in range(n):
					if i != k or j != k or i != j:
						D[i][j] = min(D[i][j], D[i][k] + D[k][j])
		for i in range(n):
			for j in range(n):
				if D[i][j] == INF:
					D[i][j] = -1


class Solution:

	def shortest_distance(self, matrix):
		(row, col) = (len(matrix), len(matrix[0]))
		for i in range(row):
			for j in range(col):
				if i == j:
					matrix[i][j] = 0
				if matrix[i][j] == -1:
					matrix[i][j] = float('inf')
		for k in range(row):
			for i in range(row):
				for j in range(col):
					matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j])
		for i in range(row):
			for j in range(col):
				if matrix[i][j] == float('inf'):
					matrix[i][j] = -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		le = len(matrix)
		for i in range(le):
			for j in range(le):
				if matrix[i][j] == -1:
					matrix[i][j] = 1000000000.0
		for via in range(le):
			for i in range(le):
				for j in range(le):
					if matrix[i][via] < 1000000000.0 and matrix[via][j] < 1000000000.0:
						matrix[i][j] = min(matrix[i][via] + matrix[via][j], matrix[i][j])
		for i in range(le):
			for j in range(le):
				if matrix[i][j] >= 1000000000.0:
					matrix[i][j] = -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		new = matrix
		n = len(new)
		for k in range(n):
			for i in range(n):
				for j in range(n):
					if new[i][k] != -1 and new[k][j] != -1:
						if new[i][j] == -1:
							new[i][j] = new[i][k] + new[k][j]
						else:
							new[i][j] = min(new[i][j], new[i][k] + new[k][j])
		return new


class Solution:

	def shortest_distance(self, m):
		n = len(m)
		s = 0
		for i in range(0, n):
			for j in range(0, n):
				if i == j:
					m[i][j] = 0
				if m[i][j] == -1:
					m[i][j] = 32767
		for k in range(0, n):
			for i in range(0, n):
				for j in range(0, n):
					s = m[i][k] + m[k][j]
					m[i][j] = min(m[i][j], s)
		for i in range(0, n):
			for j in range(0, n):
				if m[i][j] == 32767:
					m[i][j] = -1
		return m


import numpy as np

class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = np.Inf
		for i in range(n):
			for j in range(n):
				for k in range(n):
					matrix[j][k] = min(matrix[j][k], matrix[j][i] + matrix[i][k])


class Solution:

	def shortest_distance(self, matrix):
		n = len(matrix)
		for i in range(n):
			for j in range(n):
				if matrix[i][j] == -1:
					matrix[i][j] = 10 ** 8
		for via in range(n):
			for i in range(n):
				for j in range(n):
					matrix[i][j] = min(matrix[i][via] + matrix[via][j], matrix[i][j])
		for i in range(n):
			for j in range(n):
				if matrix[i][j] >= 10 ** 8:
					matrix[i][j] = -1
		return matrix


class Solution:

	def shortest_distance(self, matrix):
		v = len(matrix)
		for k in range(v):
			for i in range(v):
				for j in range(v):
					if matrix[i][k] == -1 or matrix[k][j] == -1:
						continue
					if matrix[i][j] == -1 or matrix[i][k] + matrix[k][j] < matrix[i][j]:
						matrix[i][j] = matrix[i][k] + matrix[k][j]
		return matrix


class Solution:

	def shortest_distance(self, mat):
		n = len(mat)
		for k in range(n):
			for i in range(n):
				for j in range(n):
					if mat[i][k] != -1 and mat[k][j] != -1:
						if mat[i][j] == -1:
							mat[i][j] = mat[i][k] + mat[k][j]
						else:
							mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j])