def  Dijkstra( N ,  S ,  matrix ): 
	valid  =  [ True ] * N         
	weight  =  [ 1000000 ] * N 
	weight [ S ]  =  0 
	for  i  in  range ( N ): 
		min_weight  =  1000000
		ID_min_weight  =  0
		for  j  in  range ( N ): 
			if  valid [ j ] and  weight [ j ]  <  min_weight : 
				min_weight  =  weight [ j ] 
				ID_min_weight  =  j 
		for  z  in  range ( N ): 
			if  weight [ ID_min_weight ]  +  matrix [ ID_min_weight ] [ z ]  <  weight [ z ]: 
				weight [ z ]  =  weight [ ID_min_weight ]  +  matrix[ ID_min_weight ] [ z ] 
		valid [ ID_min_weight ]  =  False 
	return  weight
matrix = [[0, 8, 2], [8, 0, 1], [2, 1, 0]]
print(Dijkstra(3, 0, matrix))
