code: 
  
  
  import math
  import sys
  
  class 						snake_case			:
  			'''simple docstring'''
  
  			def __init__(	self     :     Union[str, Any]					)					->					str:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								SCREAMING_SNAKE_CASE_	      =       0
  								SCREAMING_SNAKE_CASE_	      =       []
  								SCREAMING_SNAKE_CASE_	      =       {}  # To store the pos of node in array
  
  			def _lowercase (	self     :     Union[str, Any]					)					->					List[str]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								return self.cur_size == 0
  
  			def _lowercase (	self     :     Any							,							lowerCAmelCase_     :     Union[str, Any]					)					->					int:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								SCREAMING_SNAKE_CASE_	      =       self.left(lowerCAmelCase_					)
  								SCREAMING_SNAKE_CASE_	      =       self.right(lowerCAmelCase_					)
  								if lc < self.cur_size and self.array(lowerCAmelCase_					)[0] < self.array(lowerCAmelCase_					)[0]:
  													SCREAMING_SNAKE_CASE_	      =       lc
  								else:
  													SCREAMING_SNAKE_CASE_	      =       idx
  								if rc < self.cur_size and self.array(lowerCAmelCase_					)[0] < self.array(lowerCAmelCase_					)[0]:
  													SCREAMING_SNAKE_CASE_	      =       rc
  								if smallest != idx:
  													self.swap(lowerCAmelCase_							,							lowerCAmelCase_					)
  													self.min_heapify(lowerCAmelCase_					)
  
  			def _lowercase (	self     :     Any							,							lowerCAmelCase_     :     Any					)					->					int:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								SCREAMING_SNAKE_CASE_	      =       self.cur_size
  								self.cur_size += 1
  								self.array.append((sys.maxsize, tup[1])					)
  								self.decrease_key((sys.maxsize, tup[1])							,							tup[0]					)
  
  			def _lowercase (	self     :     List[Any]					)					->					List[Any]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								SCREAMING_SNAKE_CASE_	      =       self.array[0][1]
  								SCREAMING_SNAKE_CASE_	      =       self.array[self.cur_size - 1]
  								self.cur_size -= 1
  								self.min_heapify(1					)
  								del self.pos[min_node]
  								return min_node
  
  			def _lowercase (	self     :     Tuple							,							lowerCAmelCase_     :     List[str]					)					->					List[Any]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								return 2 * i + 1
  
  			def _lowercase (	self     :     Optional[Any]							,							lowerCAmelCase_     :     Any					)					->					str:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								return 2 * i + 2
  
  			def _lowercase (	self     :     Optional[Any]							,							lowerCAmelCase_     :     List[Any]					)					->					int:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								return math.floor(i / 2					)
  
  			def _lowercase (	self     :     Union[str, Any]							,							lowerCAmelCase_     :     str							,							lowerCAmelCase_     :     str					)					->					List[str]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								SCREAMING_SNAKE_CASE_	      =       j
  								SCREAMING_SNAKE_CASE_	      =       i
  								SCREAMING_SNAKE_CASE_	      =       self.array[i]
  								SCREAMING_SNAKE_CASE_	      =       self.array[j]
  								SCREAMING_SNAKE_CASE_	      =       temp
  
  
  
  
  			def _lowercase (	self     :     int							,							lowerCAmelCase_     :     Tuple							,							lowerCAmelCase_     :     Optional[int]					)					->					Union[str, Any]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								SCREAMING_SNAKE_CASE_	      =       self.pos[tup[1]]
  								# assuming the new_d is atmost old_d
  								SCREAMING_SNAKE_CASE_	      =       (new_d, tup[1])
  								while idx > 0 and self.array[self.par(lowerCAmelCase_					)][0] > self.array[idx][0]:
  													self.swap(lowerCAmelCase_							,							self.par(lowerCAmelCase_					)					)
  													SCREAMING_SNAKE_CASE_	      =       self.par(lowerCAmelCase_					)
  
  class 						snake_case			:
  			'''simple docstring'''
  
  			def __init__(	self     :     List[Any]							,							lowerCAmelCase_     :     int					)					->					Tuple:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								SCREAMING_SNAKE_CASE_	      =       {}  # To store graph: u -> (v,w)
  								SCREAMING_SNAKE_CASE_	      =       num  # Number of nodes in graph
  								# To store the distance from source vertex
  								SCREAMING_SNAKE_CASE_	      =       [0] * self.num_nodes
  								SCREAMING_SNAKE_CASE_	      =       [-1] * self.num_nodes  # To store the path
  
  			def _lowercase (	self     :     Union[str, Any]							,							lowerCAmelCase_     :     List[Any]							,							lowerCAmelCase_     :     Optional[Any]							,							lowerCAmelCase_     :     Optional[Any]					)					->					List[Any]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								if u in self.adjList:
  													self.adjList[u].append((v, w)					)
  								else:
  													SCREAMING_SNAKE_CASE_	      =       [(v, w)]
  
  								# Assuming undirected graph
  								if v in self.adjList:
  													self.adjList[v].append((u, w)					)
  								else:
  													SCREAMING_SNAKE_CASE_	      =       [(u, w)]
  
  			def _lowercase (	self     :     Dict					)					->					Optional[int]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								for u in self.adjList:
  													print(lowerCAmelCase_							,							'''->'''							,							''' -> '''.join(str(F'''{v}({w})'''					) for v, w in self.adjList[u]					)					)
  
  			def _lowercase (	self     :     List[Any]							,							lowerCAmelCase_     :     Any					)					->					List[str]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								SCREAMING_SNAKE_CASE_	      =       [-1] * self.num_nodes
  								# src is the source node
  								SCREAMING_SNAKE_CASE_	      =       0
  								SCREAMING_SNAKE_CASE_	      =       PriorityQueue()
  								q.insert((0, src)					)  # (dist from src, node)
  								for u in self.adjList:
  													if u != src:
  																		SCREAMING_SNAKE_CASE_	      =       sys.maxsize  # Infinity
  																		SCREAMING_SNAKE_CASE_	      =       -1
  
  								while not q.is_empty():
  													SCREAMING_SNAKE_CASE_	      =       q.extract_min()  # Returns node with the min dist from source
  													# Update the distance of all the neighbours of u and
  													# if their prev dist was INFINITY then push them in Q
  													for v, w in self.adjList[u]:
  																		SCREAMING_SNAKE_CASE_	      =       self.dist[u] + w
  																		if self.dist[v] > new_dist:
  																							if self.dist[v] == sys.maxsize:
  																												q.insert((new_dist, v)					)
  																							else:
  																												q.decrease_key((self.dist[v], v)							,							lowerCAmelCase_					)
  																							SCREAMING_SNAKE_CASE_	      =       new_dist
  																							SCREAMING_SNAKE_CASE_	      =       u
  
          # Show the shortest distances from src
  								self.show_distances(lowerCAmelCase_					)
  
  			def _lowercase (	self     :     Any							,							lowerCAmelCase_     :     Optional[int]					)					->					List[Any]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								print(F'''Distance from node: {src}'''					)
  								for u in range(self.num_nodes					):
  													print(F'''Node {u} has distance: {self.dist[u]}'''					)
  
  
  
  
  			def _lowercase (	self     :     List[str]							,							lowerCAmelCase_     :     Optional[Any]							,							lowerCAmelCase_     :     List[Any]					)					->					List[Any]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								SCREAMING_SNAKE_CASE_	      =       []
  								SCREAMING_SNAKE_CASE_	      =       0
  								SCREAMING_SNAKE_CASE_	      =       dest
  								# Backtracking from dest to src
  								while self.par[temp] != -1:
  													path.append(lowerCAmelCase_					)
  													if temp != src:
  																		for v, w in self.adjList[temp]:
  																							if v == self.par[temp]:
  																												cost += w
  																												break
  													SCREAMING_SNAKE_CASE_	      =       self.par[temp]
  								path.append(lowerCAmelCase_					)
  								path.reverse()
  
  								print(F'''----Path to reach {dest} from {src}----'''					)
  								for u in path:
  													print(F'''{u}'''							,							end=''' '''					)
  													if u != dest:
  																		print('''-> '''							,							end=''''''					)
  
  								print('''\nTotal cost of path: '''							,							lowerCAmelCase_					)
  
  
  if __name__ == "__main__":
  		A_														=      Graph(9)
  		graph.add_edge(0, 1, 4)
  		graph.add_edge(0, 7, 8)
  		graph.add_edge(1, 2, 8)
  		graph.add_edge(1, 7, 1_1)
  		graph.add_edge(2, 3, 7)
  		graph.add_edge(2, 8, 2)
  		graph.add_edge(2, 5, 4)
  		graph.add_edge(3, 4, 9)
  		graph.add_edge(3, 5, 1_4)
  		graph.add_edge(4, 5, 1_0)
  		graph.add_edge(5, 6, 2)
  		graph.add_edge(6, 7, 1)
  		graph.add_edge(6, 8, 6)
  		graph.add_edge(7, 8, 7)
  		graph.show_graph()
  		graph.dijkstra(0)
  		graph.show_path(0, 4)
  
  # OUTPUT
  # 0 -> 1(4) -> 7(8)
  # 1 -> 0(4) -> 2(8) -> 7(11)
  # 7 -> 0(8) -> 1(11) -> 6(1) -> 8(7)
  # 2 -> 1(8) -> 3(7) -> 8(2) -> 5(4)
  # 3 -> 2(7) -> 4(9) -> 5(14)
  # 8 -> 2(2) -> 6(6) -> 7(7)
  # 5 -> 2(4) -> 3(14) -> 4(10) -> 6(2)
  # 4 -> 3(9) -> 5(10)
  # 6 -> 5(2) -> 7(1) -> 8(6)
  # Distance from node: 0
  # Node 0 has distance: 0
  # Node 1 has distance: 4
  # Node 2 has distance: 12
  # Node 3 has distance: 19
  # Node 4 has distance: 21
  # Node 5 has distance: 11
  # Node 6 has distance: 9
  # Node 7 has distance: 8
  # Node 8 has distance: 14
  # ----Path to reach 4 from 0----
  # 0 -> 7 -> 6 -> 5 -> 4
  # Total cost of path:  21
  
  
  
style_context: 
  
  
  import json
  import os
  from collections.abc import Mapping
  from typing import Dict, List, Optional, Union
  
  import numpy as np
  import torch
  
  from .imports import is_safetensors_available
  
  
  
  
  
  
  
  def 							UpperCAmelCase				(     UpperCAmelCase				,UpperCAmelCase				,UpperCAmelCase				,UpperCAmelCase=None      )->		Dict:
  
  
  
  
  
  
  
  					'''simple docstring'''
  
  
  
  					SCREAMING_SNAKE_CASE_	      =       None
  					# Check the string instead of the dtype to be compatible with versions of PyTorch that don't have bfloat16.
  					if str(weight.dtype      ) == "torch.bfloat16":
  										# Need to reinterpret the underlined data as int16 since NumPy does not handle bfloat16s.
  										SCREAMING_SNAKE_CASE_	      =       weight.view(torch.intaa      )
  										SCREAMING_SNAKE_CASE_	      =       '''bfloat16'''
  					SCREAMING_SNAKE_CASE_	      =       weight.cpu().numpy()
  					SCREAMING_SNAKE_CASE_	      =       os.path.join(UpperCAmelCase				,f'''{weight_name}.dat'''      )
  					if index is not None:
  										if dtype is None:
  															SCREAMING_SNAKE_CASE_	      =       str(array.dtype      )
  										SCREAMING_SNAKE_CASE_	      =       {'''dtype''': dtype, '''shape''': list(array.shape      )}
  					if array.ndim == 0:
  										SCREAMING_SNAKE_CASE_	      =       array[None]
  					SCREAMING_SNAKE_CASE_	      =       np.memmap(UpperCAmelCase				,dtype=array.dtype				,mode='''w+'''				,shape=array.shape      )
  					SCREAMING_SNAKE_CASE_	      =       array[:]
  					file_array.flush()
  					return index
  
  
  
  
  
  
  
  def 							UpperCAmelCase				(     UpperCAmelCase				,UpperCAmelCase      )->		List[str]:
  
  
  
  
  
  
  
  					'''simple docstring'''
  
  
  
  					SCREAMING_SNAKE_CASE_	      =       tuple(weight_info['''shape''']      )
  					if shape == ():
  										# NumPy memory-mapped arrays can't have 0 dims so it was saved as 1d tensor
  										SCREAMING_SNAKE_CASE_	      =       (1,)
  
  					SCREAMING_SNAKE_CASE_	      =       weight_info['''dtype''']
  					if dtype == "bfloat16":
  										# NumPy does not support bfloat16 so this was saved as a int16
  										SCREAMING_SNAKE_CASE_	      =       '''int16'''
  
  					SCREAMING_SNAKE_CASE_	      =       np.memmap(UpperCAmelCase				,dtype=UpperCAmelCase				,shape=UpperCAmelCase				,mode='''r'''      )
  
  					if len(weight_info['''shape''']      ) == 0:
  										SCREAMING_SNAKE_CASE_	      =       weight[0]
  					SCREAMING_SNAKE_CASE_	      =       torch.tensor(UpperCAmelCase      )
  					if weight_info["dtype"] == "bfloat16":
  										SCREAMING_SNAKE_CASE_	      =       weight.view(torch.bfloataa      )
  
  					return weight
  
  
  
  
  
  
  
  def 							UpperCAmelCase				(     UpperCAmelCase				,UpperCAmelCase      )->		str:
  
  
  
  
  
  
  
  					'''simple docstring'''
  
  
  
  					if index is None or len(UpperCAmelCase      ) == 0:
  										# Nothing to save
  										return
  
  					SCREAMING_SNAKE_CASE_	      =       os.path.join(UpperCAmelCase				,'''index.json'''      )
  					if os.path.isfile(UpperCAmelCase      ):
  										with open(UpperCAmelCase				,'''r'''				,encoding='''utf-8'''      ) as f:
  															SCREAMING_SNAKE_CASE_	      =       json.load(UpperCAmelCase      )
  					else:
  										SCREAMING_SNAKE_CASE_	      =       {}
  					current_index.update(UpperCAmelCase      )
  
  					with open(UpperCAmelCase				,'''w'''				,encoding='''utf-8'''      ) as f:
  										json.dump(UpperCAmelCase				,UpperCAmelCase				,indent=2      )
  
  
  
  
  
  
  
  def 							UpperCAmelCase				(     UpperCAmelCase				,UpperCAmelCase      )->		Optional[Any]:
  
  
  
  
  
  
  
  					'''simple docstring'''
  
  
  
  					os.makedirs(UpperCAmelCase				,exist_ok=UpperCAmelCase      )
  					SCREAMING_SNAKE_CASE_	      =       {}
  					for name, parameter in state_dict.items():
  										SCREAMING_SNAKE_CASE_	      =       offload_weight(UpperCAmelCase				,UpperCAmelCase				,UpperCAmelCase				,index=UpperCAmelCase      )
  
  					# Update index
  					save_offload_index(UpperCAmelCase				,UpperCAmelCase      )
  
  class 						snake_case			(       lowerCAmelCase__	):
  			'''simple docstring'''
  
  			def __init__(	self     :     int							,							lowerCAmelCase_     :     Mapping							,							lowerCAmelCase_     :     str					)					->					Dict:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								SCREAMING_SNAKE_CASE_	      =       dataset
  								SCREAMING_SNAKE_CASE_	      =       prefix
  
  			def __getitem__(	self     :     Optional[int]							,							lowerCAmelCase_     :     Optional[int]					)					->					Union[str, Any]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								return self.dataset[F'''{self.prefix}{key}''']
  
  			def __iter__(	self     :     Tuple					)					->					str:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								return iter([key for key in self.dataset if key.startswith(self.prefix					)]					)
  
  
  
  
  			def __len__(	self     :     Dict					)					->					Optional[int]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								return len(self.dataset					)
  
  class 						snake_case			(       lowerCAmelCase__	):
  			'''simple docstring'''
  
  			def __init__(	self     :     int							,							lowerCAmelCase_     :     Dict[str, torch.Tensor] = None							,							lowerCAmelCase_     :     Optional[Union[str, os.PathLike]] = None							,							lowerCAmelCase_     :     Mapping = None							,							lowerCAmelCase_     :     int=None							,							)					->					Tuple:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								if state_dict is None and save_folder is None:
  													raise ValueError('''Need either a `state_dict` or a `save_folder` containing offloaded weights.'''					)
  
  								SCREAMING_SNAKE_CASE_	      =       {} if state_dict is None else state_dict
  								SCREAMING_SNAKE_CASE_	      =       save_folder
  								if index is None and save_folder is not None:
  													with open(os.path.join(lowerCAmelCase_							,							'''index.json'''					)					) as f:
  																		SCREAMING_SNAKE_CASE_	      =       json.load(lowerCAmelCase_					)
  								SCREAMING_SNAKE_CASE_	      =       {} if index is None else index
  								SCREAMING_SNAKE_CASE_	      =       list(self.state_dict.keys()					)
  								self.all_keys.extend([key for key in self.index if key not in self.all_keys]					)
  								SCREAMING_SNAKE_CASE_	      =       device
  
  			def __getitem__(	self     :     str							,							lowerCAmelCase_     :     str					)					->					Union[str, Any]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								if key in self.state_dict:
  													return self.state_dict[key]
  								SCREAMING_SNAKE_CASE_	      =       self.index[key]
  								if weight_info.get('''safetensors_file'''					) is not None:
  													if not is_safetensors_available():
  																		raise ImportError('''These offloaded weights require the use of safetensors: `pip install safetensors`.'''					)
  
  													from safetensors import safe_open
  
  													SCREAMING_SNAKE_CASE_	      =       '''cpu''' if self.device is None else self.device
  													with safe_open(weight_info['''safetensors_file''']							,							framework='''pt'''							,							device=lowerCAmelCase_					) as f:
  																		SCREAMING_SNAKE_CASE_	      =       f.get_tensor(weight_info.get('''weight_name'''							,							lowerCAmelCase_					)					)
  
  													if "dtype" in weight_info:
  																		return tensor.to(getattr(lowerCAmelCase_							,							weight_info['''dtype''']					)					)
  													else:
  																		return tensor
  
  								SCREAMING_SNAKE_CASE_	      =       os.path.join(self.save_folder							,							F'''{key}.dat'''					)
  								return load_offloaded_weight(lowerCAmelCase_							,							lowerCAmelCase_					)
  
  			def __iter__(	self     :     str					)					->					Optional[int]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								return iter(self.all_keys					)
  
  
  
  
  			def __len__(	self     :     Optional[Any]					)					->					Optional[Any]:
  
  
  
  
  								"""simple docstring"""
  
  
  
  
  
  
  								return len(self.all_keys					)
  
  
  
  
  
  
  
  def 							UpperCAmelCase				(     UpperCAmelCase				,UpperCAmelCase      )->		List[str]:
  
  
  
  
  
  
  
  					'''simple docstring'''
  
  
  
  					SCREAMING_SNAKE_CASE_	      =       {}
  					for module_name in submodule_names:
  										# We want to catch module_name parameter (module_name.xxx) or potentially module_name, but not any of the
  										# submodules that could being like module_name (transformers.h.1 and transformers.h.10 for instance)
  										result.update(
  										    {
  										        key: param
  										        for key, param in state_dict.items()
  										        if key == module_name or key.startswith(module_name + '''.'''      )
  										    }      )
  					return result
  
  
  