import sys
class Graph:
	def __init__(self,graph,edge):
		self.graph=graph
		self.edge=edge

		self.w=[[sys.maxsize]*len(self.graph) for i in range(len(self.graph))]
		for i in range(len(self.w)):
			for j in range(len(self.w)):
				if(i==j):self.w[i][j]=0
				if self.edge.get( (i,j) ): self.w[i][j]=self.edge[i,j]

	def Floyd_Warshall(self):
		n=len(self.w)
		D=[list(self.w)for i in range(n)]
		D0=list(self.w)
		p0=[[0]*n for i in range(n)]
		p=[list(p0) for i in range(n)]
		for i in range(n):
			for j in range(n):
				if i==j or not self.edge.get( (i,j) ) : p0[i][j]=None
				else: p0[i][j]=i
		print(p0)
		for k in range(len(D)):
			for i in range(0,n):
				for j in range(0,n):
					if (k):
						D[k][i][j]=min(D[k-1][i][j],D[k-1][i][k]+D[k-1][k][j])
						if D[k][i][j]== (D[k-1][i][k]+D[k-1][k][j]) : p[k][i][j]=p[k-1][k][j]
						else:	p[k][i][j]=p[k-1][i][j]
		
					else:
						D[0][i][j]=min(D0[i][j],D0[i][0]+D0[0][j])
						if D[0][i][j]==(D0[i][0]+D0[0][j]) : p[0][i][j]=p0[0][j] 
						else:	p[0][i][j]=p0[i][j]
		print(p0)
		return D[n-1],p0
edge={(0,1):6,(0,2):-1,(1,0):2,(1,2):2,(2,1):3}
graph={0:[1,2],1:[0,2],2:[1]}
G=Graph(graph,edge)
G.Floyd_Warshall()# your code goes here