

def  snake_case_(_UpperCamelCase					,			_UpperCamelCase	)				->      Any:



  """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  snake_case_(_UpperCamelCase					,			_UpperCamelCase					,			_UpperCamelCase	)				->      Any:



  """simple docstring"""






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



def  snake_case_(_UpperCamelCase					,			_UpperCamelCase					,			_UpperCamelCase	)				->      Tuple:



  """simple docstring"""






  _snake_case		=				[float('''inf'''	) for _ in range(_UpperCamelCase	)]
  _snake_case		=				[False for _ in range(_UpperCamelCase	)]
  _snake_case		=				0.0

  for _ in range(v - 1	):
    _snake_case		=				min_dist(_UpperCamelCase					,			_UpperCamelCase					,			_UpperCamelCase	)
    _snake_case		=				True

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

  print_dist(_UpperCamelCase					,			_UpperCamelCase	)


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

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

 for i in range(V):
  __A     						=      0.0

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

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




from __future__ import annotations



def  snake_case_(_UpperCamelCase					,			_UpperCamelCase					,			_UpperCamelCase	)				->      int:



  """simple docstring"""






  assert n > 1 and a > 0 and greatest_common_divisor(_UpperCamelCase					,			_UpperCamelCase	) == 1
  ((_snake_case),	(_snake_case),	(_snake_case))		=				extended_gcd(_UpperCamelCase					,			_UpperCamelCase	)  # Implemented below
  _snake_case		=				(b * s) % n
  return x



def  snake_case_(_UpperCamelCase					,			_UpperCamelCase	)				->      int:



  """simple docstring"""






  ((_snake_case),	(_snake_case))		=				extended_euclid(_UpperCamelCase					,			_UpperCamelCase	)  # Implemented below
  if b < 0:
    _snake_case		=				(b % n + n) % n
  return b



def  snake_case_(_UpperCamelCase					,			_UpperCamelCase					,			_UpperCamelCase	)				->      int:



  """simple docstring"""






  _snake_case		=				invert_modulo(_UpperCamelCase					,			_UpperCamelCase	)
  _snake_case		=				(b * s) % n
  return x



def  snake_case_(_UpperCamelCase					,			_UpperCamelCase	)				->      tuple[int, int, int]:



  """simple docstring"""






  assert a >= 0 and b >= 0

  if b == 0:
    _snake_case,	_snake_case,	_snake_case		=				a, 1, 0
  else:
    ((_snake_case),	(_snake_case),	(_snake_case))		=				extended_gcd(_UpperCamelCase					,			a % b	)
    _snake_case		=				q
    _snake_case		=				p - q * (a // b)

  assert a % d == 0 and b % d == 0
  assert d == a * x + b * y

  return (d, x, y)



def  snake_case_(_UpperCamelCase					,			_UpperCamelCase	)				->      tuple[int, int]:



  """simple docstring"""






  if b == 0:
    return (1, 0)
  ((_snake_case),	(_snake_case))		=				extended_euclid(_UpperCamelCase					,			a % b	)
  _snake_case		=				a // b
  return (y, x - k * y)



def  snake_case_(_UpperCamelCase					,			_UpperCamelCase	)				->      int:



  """simple docstring"""






  if a < b:
    _snake_case,	_snake_case		=				b, a

  while a % b != 0:
    _snake_case,	_snake_case		=				b, a % b

  return b


if __name__ == "__main__":
 from doctest import testmod

 testmod(name='''modular_division''', verbose=True)
 testmod(name='''modular_division2''', verbose=True)
 testmod(name='''invert_modulo''', verbose=True)
 testmod(name='''extended_gcd''', verbose=True)
 testmod(name='''extended_euclid''', verbose=True)
 testmod(name='''greatest_common_divisor''', verbose=True)

