"""simple docstring"""







def   __lowerCAmelCase(		__UpperCAmelCase  ,__UpperCAmelCase      ):






	"""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   __lowerCAmelCase(		__UpperCAmelCase  ,__UpperCAmelCase  ,__UpperCAmelCase      ):






	"""simple docstring"""





	_lowercase			:     Optional[int]      					=				float('inf'      )
	_lowercase			:     List[str]      					=				-1
	for i in range(__UpperCAmelCase      ):
		if (not vset[i]) and mdist[i] < min_val:
			_lowercase			:     Optional[int]      					=				i
			_lowercase			:     Dict      					=				mdist[i]
	return min_ind


def   __lowerCAmelCase(		__UpperCAmelCase  ,__UpperCAmelCase  ,__UpperCAmelCase      ):






	"""simple docstring"""





	_lowercase			:     Optional[Any]      					=				[float('inf'      ) for _ in range(__UpperCAmelCase      )]
	_lowercase			:     Dict      					=				[False for _ in range(__UpperCAmelCase      )]
	_lowercase			:     Tuple      					=				0.0

	for _ in range(v - 1      ):
		_lowercase			:     List[str]      					=				min_dist(__UpperCAmelCase  ,__UpperCAmelCase  ,__UpperCAmelCase      )
		_lowercase			:     int      					=				True

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

	print_dist(__UpperCAmelCase  ,__UpperCAmelCase      )


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

						SCREAMING_SNAKE_CASE						=    [[float('inf') for i in range(V)] for j in range(V)]

						for i in range(V):
												SCREAMING_SNAKE_CASE						=    0.0

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

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




"""simple docstring"""







from __future__ import annotations

import math
import random


def   __lowerCAmelCase(		__UpperCAmelCase  ,__UpperCAmelCase  ,__UpperCAmelCase      ):






	"""simple docstring"""





	_lowercase			:     Optional[int]      					=				d * e - 1
	_lowercase			:     int      					=				0
	_lowercase			:     Union[str, Any]      					=				0
	while p == 0:
		_lowercase			:     int      					=				random.randint(2  ,n - 1      )
		_lowercase			:     str      					=				k
		while True:
			if t % 2 == 0:
				_lowercase			:     List[Any]      					=				t // 2
				_lowercase			:     int      					=				(g**t) % n
				_lowercase			:     Tuple      					=				math.gcd(x - 1  ,__UpperCAmelCase      )
				if x > 1 and y > 1:
					_lowercase			:     List[str]      					=				y
					_lowercase			:     str      					=				n // y
					break  # find the correct factors
			else:
				break  # t is not divisible by 2, break and choose another g
	return sorted([p, q]      )


if __name__ == "__main__":
						import doctest

						doctest.testmod()



