



def 							A     (						__UpperCAmelCase				,   __UpperCAmelCase      )			->			list[list[int]]:



						'''simple docstring'''






						UpperCAmelCase_					=	[]
						UpperCAmelCase_					=	len(__UpperCAmelCase      )
						for i in range(__UpperCAmelCase      ):
												UpperCAmelCase_					=	[]
												for j in range(__UpperCAmelCase      ):
																		UpperCAmelCase_					=	0
																		for k in range(__UpperCAmelCase      ):
																								UpperCAmelCase_					=	val + matrix_a[i][k] * matrix_b[k][j]
																		list_a.append(__UpperCAmelCase      )
												matrix_c.append(__UpperCAmelCase      )
						return matrix_c







def 							A     (						__UpperCAmelCase      )			->			list[list[int]]:



						'''simple docstring'''






						return [[int(row == column      ) for column in range(__UpperCAmelCase      )] for row in range(__UpperCAmelCase      )]







def 							A     (						__UpperCAmelCase      )			->			int:



						'''simple docstring'''






						if n <= 1:
												return n
						UpperCAmelCase_					=	identity(2      )
						UpperCAmelCase_					=	[[1, 1], [1, 0]]
						UpperCAmelCase_					=	n - 1
						while n > 0:
												if n % 2 == 1:
																		UpperCAmelCase_					=	multiply(__UpperCAmelCase				,   __UpperCAmelCase      )
												UpperCAmelCase_					=	multiply(__UpperCAmelCase				,   __UpperCAmelCase      )
												UpperCAmelCase_					=	int(n / 2      )
						return res_matrix[0][0]







def 							A     (						__UpperCAmelCase      )			->			int:



						'''simple docstring'''






						if n <= 1:
												return n
						UpperCAmelCase_					=	0
						UpperCAmelCase_					=	1
						for _ in range(2				,   n + 1      ):
												UpperCAmelCase_				, UpperCAmelCase_					=	fiba, fiba + fiba
						return fiba







def 							A     (						)			->			None:



						'''simple docstring'''






						for ordinal in "0th 1st 2nd 3rd 10th 100th 1000th".split():
												UpperCAmelCase_					=	int(''''''.join(c for c in ordinal if c in '''0123456789'''      )      )  # 1000th --> 1000
												print(
												    f"{ordinal} fibonacci number using matrix exponentiation is "
												    f"{nth_fibonacci_matrix(__UpperCAmelCase      )} and using bruteforce is "
												    f"{nth_fibonacci_bruteforce(__UpperCAmelCase      )}\n"      )
						# from timeit import timeit
						# print(timeit("nth_fibonacci_matrix(1000000)",
						#              "from main import nth_fibonacci_matrix", number=5))
						# print(timeit("nth_fibonacci_bruteforce(1000000)",
						#              "from main import nth_fibonacci_bruteforce", number=5))
						# 2.3342058970001744
						# 57.256506615000035


if __name__ == "__main__":
							import doctest

							doctest.testmod()
							main()










def 							A     (						__UpperCAmelCase				,   __UpperCAmelCase      )			->			int:



						'''simple docstring'''






						print('''\nVertex Distance'''      )
						for i in range(__UpperCAmelCase      ):
												if dist[i] != float('''inf'''      ):
																		print(__UpperCAmelCase				,   '''\t'''				,   int(dist[i]      )				,   end='''\t'''      )
												else:
																		print(__UpperCAmelCase				,   '''\t'''				,   '''INF'''				,   end='''\t'''      )
												print()







def 							A     (						__UpperCAmelCase				,   __UpperCAmelCase				,   __UpperCAmelCase      )			->			str:



						'''simple docstring'''






						UpperCAmelCase_					=	float('''inf'''      )
						UpperCAmelCase_					=	-1
						for i in range(__UpperCAmelCase      ):
												if (not vset[i]) and mdist[i] < min_val:
																		UpperCAmelCase_					=	i
																		UpperCAmelCase_					=	mdist[i]
						return min_ind







def 							A     (						__UpperCAmelCase				,   __UpperCAmelCase				,   __UpperCAmelCase      )			->			Optional[Any]:



						'''simple docstring'''






						UpperCAmelCase_					=	[float('''inf'''      ) for _ in range(__UpperCAmelCase      )]
						UpperCAmelCase_					=	[False for _ in range(__UpperCAmelCase      )]
						UpperCAmelCase_					=	0.0

						for _ in range(v - 1      ):
												UpperCAmelCase_					=	min_dist(__UpperCAmelCase				,   __UpperCAmelCase				,   __UpperCAmelCase      )
												UpperCAmelCase_					=	True

												for i in range(__UpperCAmelCase      ):
																		if (
																		    (not vset[i])
																		    and graph[u][i] != float('''inf'''      )
																		    and mdist[u] + graph[u][i] < mdist[i]
																		):
																								UpperCAmelCase_					=	mdist[u] + graph[u][i]

						print_dist(__UpperCAmelCase				,   __UpperCAmelCase      )


if __name__ == "__main__":
							UpperCamelCase_      			=  int(input("Enter number of vertices: ").strip())
							UpperCamelCase_      			=  int(input("Enter number of edges: ").strip())

							UpperCamelCase_      			=  [[float("inf") for i in range(V)] for j in range(V)]

							for i in range(V):
														UpperCamelCase_      			=  0.0

							for i in range(E):
														print("\nEdge ", i + 1)
														UpperCamelCase_      			=  int(input("Enter source:").strip())
														UpperCamelCase_      			=  int(input("Enter destination:").strip())
														UpperCamelCase_      			=  float(input("Enter weight:").strip())
														UpperCamelCase_      			=  weight

							UpperCamelCase_      			=  int(input("\nEnter shortest path source:").strip())
							dijkstra(graph, V, gsrc)





