





import os
from typing import Optional

import fsspec
from fsspec.archive import AbstractArchiveFileSystem
from fsspec.utils import DEFAULT_BLOCK_SIZE


class       __lowerCAmelCase					(       _UpperCamelCase      ):


	'''simple docstring'''





	_A													=				""
	_A													=				(
	    None  # protocol passed in prefix to the url. ex: "gzip", for gzip://file.txt::http://foo.bar/file.txt.gz
	)
	_A													=				None  # compression type in fsspec. ex: "gzip"
	_A													=				None  # extension of the filename to strip. ex: "".gz" to get file.txt from file.txt.gz

	def __init__(						self:						Union[str, Any],					lowerCamelCase_:						str = "",					lowerCamelCase_:						Optional[str] = None,					lowerCamelCase_:						Optional[dict] = None,					**lowerCamelCase_:						int			):
			super().__init__(self,					**lowerCamelCase_			)
			# always open as "rb" since fsspec can then use the TextIOWrapper to make it work for "r" mode
			lowercase__					:      Dict      =		fsspec.open(
			    lowerCamelCase_,					mode='rb',					protocol=lowerCamelCase_,					compression=self.compression,					client_kwargs={
			        'requote_redirect_url': False,  # see https://github.com/huggingface/datasets/pull/5459
			        'trust_env': True,  # Enable reading proxy env variables.
			        **(target_options or {}).pop('client_kwargs',					{}			),  # To avoid issues if it was already passed.
			    },					**(target_options or {}),					)
			lowercase__					:      List[Any]      =		os.path.basename(self.file.path.split('::'			)[0]			)
			lowercase__					:      Optional[int]      =		(
			    self.compressed_name[: self.compressed_name.rindex('.'			)]
			    if '.' in self.compressed_name
			    else self.compressed_name
			)
			lowercase__					:      str      =		None

	@classmethod
	def    snake_case__(						cls:						Optional[int],					lowerCamelCase_:						List[Any]			):
			# compressed file paths are always relative to the archive root
			return super()._strip_protocol(lowerCamelCase_			).lstrip('/'			)

	def    snake_case__(						self:						Union[str, Any]			):
			if self.dir_cache is None:
					lowercase__					:      Optional[Any]      =		{**self.file.fs.info(self.file.path			), 'name': self.uncompressed_name}
					lowercase__					:      Tuple      =		{f['name']: f}

	def    snake_case__(						self:						int,					lowerCamelCase_:						str			):
			return self.file.open().read()





	def    snake_case__(						self:						Optional[Any],					lowerCamelCase_:						str,					lowerCamelCase_:						str = "rb",					lowerCamelCase_:						Optional[int]=None,					lowerCamelCase_:						Union[str, Any]=True,					lowerCamelCase_:						Optional[Any]=None,					**lowerCamelCase_:						Tuple,					):
			lowercase__					:      List[str]      =		self._strip_protocol(lowerCamelCase_			)
			if mode != "rb":
					raise ValueError(F"""Tried to read with mode {mode} on file {self.file.path} opened with mode 'rb'"""			)
			return self.file.open()


class       __lowerCAmelCase					(       _UpperCamelCase      ):


	'''simple docstring'''





	_A													=				"bz2"
	_A													=				"bz2"
	_A													=				".bz2"


class       __lowerCAmelCase					(       _UpperCamelCase      ):


	'''simple docstring'''





	_A													=				"gzip"
	_A													=				"gzip"
	_A													=				".gz"


class       __lowerCAmelCase					(       _UpperCamelCase      ):


	'''simple docstring'''





	_A													=				"lz4"
	_A													=				"lz4"
	_A													=				".lz4"


class       __lowerCAmelCase					(       _UpperCamelCase      ):


	'''simple docstring'''





	_A													=				"xz"
	_A													=				"xz"
	_A													=				".xz"


class       __lowerCAmelCase					(       _UpperCamelCase      ):


	'''simple docstring'''





	_A													=				"zstd"
	_A													=				"zstd"
	_A													=				".zst"

	def __init__(						self:						Union[str, Any],					lowerCamelCase_:						str,					lowerCamelCase_:						str = "rb",					lowerCamelCase_:						Optional[str] = None,					lowerCamelCase_:						Optional[dict] = None,					lowerCamelCase_:						int = DEFAULT_BLOCK_SIZE,					**lowerCamelCase_:						List[str],					):
			super().__init__(
			    fo=lowerCamelCase_,					mode=lowerCamelCase_,					target_protocol=lowerCamelCase_,					target_options=lowerCamelCase_,					block_size=lowerCamelCase_,					**lowerCamelCase_,					)
			# We need to wrap the zstd decompressor to avoid this error in fsspec==2021.7.0 and zstandard==0.15.2:
			#
			# File "/Users/user/.virtualenvs/hf-datasets/lib/python3.7/site-packages/fsspec/core.py", line 145, in open
			#     out.close = close
			# AttributeError: 'zstd.ZstdDecompressionReader' object attribute 'close' is read-only
			#
			# see https://github.com/intake/filesystem_spec/issues/725
			lowercase__					:      Tuple      =		self.file.__enter__


			class       __lowerCAmelCase					:


				'''simple docstring'''





				def __init__(						self:						List[Any],					lowerCamelCase_:						str			):
						lowercase__					:      Tuple      =		file_

				def __enter__(						self:						List[Any]			):
						self._file.__enter__()
						return self

				def __exit__(						self:						Tuple,					*lowerCamelCase_:						Optional[Any],					**lowerCamelCase_:						str			):
						self._file.__exit__(*lowerCamelCase_,					**lowerCamelCase_			)

				def __iter__(						self:						Tuple			):
						return iter(self._file			)

				def    snake_case__(						self:						Optional[Any]			):
						return next(self._file			)





				def __getattr__(						self:						int,					lowerCamelCase_:						List[str]			):
						return getattr(self._file,					lowerCamelCase_			)

			def fixed_enter(*lowerCamelCase_:						Union[str, Any],					**lowerCamelCase_:						Union[str, Any]			):
					return WrappedFile(_enter(*lowerCamelCase_,					**lowerCamelCase_			)			)

			lowercase__					:      List[str]      =		fixed_enter









from __future__ import annotations


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : list[float]   ,    _lowercase     : Tuple			)   ->							int:




		'''simple docstring'''
		print(f"""Vertex\tShortest Distance from vertex {src}"""			)
		for i, d in enumerate(_lowercase			):
				print(f"""{i}\t\t{d}"""			)


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : list[dict[str, int]]   ,    _lowercase     : list[float]   ,    _lowercase     : int			)   ->							Any:




		'''simple docstring'''
		for j in range(_lowercase			):
				lowercase__   ,				lowercase__   ,				lowercase__					:      Dict      =		(graph[j][k] for k in ['src', 'dst', 'weight'])
				if distance[u] != float('inf'			) and distance[u] + w < distance[v]:
						return True
		return False


def       SCREAMING_SNAKE_CASE__  (       _lowercase     : list[dict[str, int]]   ,    _lowercase     : int   ,    _lowercase     : int   ,    _lowercase     : int			)   ->							list[float]:




		'''simple docstring'''
		lowercase__					:      Dict      =		[float('inf'			)] * vertex_count
		lowercase__					:      Dict      =		0.0

		for _ in range(vertex_count - 1			):
				for j in range(_lowercase			):
						lowercase__   ,				lowercase__   ,				lowercase__					:      int      =		(graph[j][k] for k in ['src', 'dst', 'weight'])

						if distance[u] != float('inf'			) and distance[u] + w < distance[v]:
								lowercase__					:      str      =		distance[u] + w

		lowercase__					:      str      =		check_negative_cycle(_lowercase   ,    _lowercase   ,    _lowercase			)
		if negative_cycle_exists:
				raise Exception('Negative cycle found'			)

		return distance


if __name__ == "__main__":
			import doctest

			doctest.testmod()

			__UpperCamelCase:	Optional[int] = int(input("""Enter number of vertices: """).strip())
			__UpperCamelCase:	Union[str, Any] = int(input("""Enter number of edges: """).strip())

			__UpperCamelCase:	list[dict[str, int]] = [{} for _ in range(E)]

			for i in range(E):
						print("""Edge """, i + 1)
						__UpperCamelCase,	__UpperCamelCase,	__UpperCamelCase:	List[str] = (
						    int(x)
						    for x in input("""Enter source, destination, weight: """).strip().split(""" """)
						)
						__UpperCamelCase:	List[Any] = {"""src""": src, """dst""": dest, """weight""": weight}

			__UpperCamelCase:	Optional[int] = int(input("""\nEnter shortest path source:""").strip())
			__UpperCamelCase:	Dict = bellman_ford(graph, V, E, source)
			print_distance(shortest_distance, 0)


