code: 
  
  
  
  
  
  """simple docstring"""
  
  
  
  
  import importlib.util
  import weakref
  from functools import partialmethod
  
  from .dependency_versions_check import dep_version_check
  from .utils import is_accelerate_available, is_torch_available, logging
  
  
  if is_torch_available():
    import torch
  
  __A :		Dict      							=    logging.get_logger(__name__)
  def 					A_			(		):
  
  
  
  
  
  
  
      '''simple docstring'''
      return importlib.util.find_spec("""deepspeed"""    ) is not None
  
  
  if is_accelerate_available() and is_deepspeed_available():
    from accelerate.utils.deepspeed import HfDeepSpeedConfig as DeepSpeedConfig
  else:
    # Inherits from a dummy `object` if accelerate is not available, so that python succeeds to import this file.
    # Deepspeed glue code will never inherit this dummy object as it checks if accelerate is available.
    from builtins import object as DeepSpeedConfig
  class 							lowerCamelCase		( lowercase__				):
  
  
  
  
  
  
  
     def __init__(							self    ,      SCREAMING_SNAKE_CASE_ ):
         # set global weakref object
         set_hf_deepspeed_config(self )
         dep_version_check("""accelerate""" )
         dep_version_check("""deepspeed""" )
         super().__init__(_A )
  
  
  
  
  
  
  
  class 							lowerCamelCase		( lowercase__				):
  
  
  
  
  
  
  
     def __init__(							self    ,      SCREAMING_SNAKE_CASE_ ):
         super().__init__(_A )
         UpperCamelCase				:   List[str]          =							None
         UpperCamelCase				:   List[Any]          =							[]
  
  
  
  
  
  
  
     def       a_							(							self ):
         if self._dtype is None:
             raise ValueError("""trainer_config_process() wasn\'t called yet to tell dtype""" )
         return self._dtype
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_ ):
         UpperCamelCase				:   Any          =							self.get_value(_A )
         if val is None:
             return False
         else:
             return val == "auto"
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_=None    ,      SCREAMING_SNAKE_CASE_=True ):
         UpperCamelCase				:   Tuple          =							self.find_config_node(_A )
         if config is None:
             return
  
         if config.get(_A ) == "auto":
             UpperCamelCase				:   Dict          =							hf_val
             return
  
         if not must_match:
             return
  
         UpperCamelCase				:   Union[str, Any]          =							config.get(_A )
         if ds_val is not None and ds_val != hf_val:
             self.mismatches.append(f'- ds {ds_key_long}={ds_val} vs hf {hf_key}={hf_val}' )
  
     lowercase       :  Dict      =				partialmethod(lowercase__	,  must_match=lowercase__				)
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_ ):
         UpperCamelCase				:   str          =							args.world_size * args.per_device_train_batch_size * args.gradient_accumulation_steps
         self.fill_match(
             """train_micro_batch_size_per_gpu"""    ,      args.per_device_train_batch_size    ,      """per_device_train_batch_size""" )
         self.fill_match("""gradient_accumulation_steps"""    ,      args.gradient_accumulation_steps    ,      """gradient_accumulation_steps""" )
         self.fill_match("""train_batch_size"""    ,      _A    ,      """train_batch_size (calculated)""" )
         self.fill_match("""gradient_clipping"""    ,      args.max_grad_norm    ,      """max_grad_norm""" )
  
         self.fill_match("""optimizer.params.lr"""    ,      args.learning_rate    ,      """learning_rate""" )
         self.fill_match("""optimizer.params.betas"""    ,      [args.adam_betaa, args.adam_betaa]    ,      """adam_beta1+adam_beta2""" )
         self.fill_match("""optimizer.params.eps"""    ,      args.adam_epsilon    ,      """adam_epsilon""" )
         self.fill_match("""optimizer.params.weight_decay"""    ,      args.weight_decay    ,      """weight_decay""" )
  
         self.fill_only("""scheduler.params.warmup_min_lr"""    ,      0 )  # not a trainer arg
         self.fill_match("""scheduler.params.warmup_max_lr"""    ,      args.learning_rate    ,      """learning_rate""" )
         # total_num_steps - will get set in trainer_config_finalize
  
         # fp16
         if args.fpaa or args.fpaa_full_eval:
             UpperCamelCase				:   Tuple          =							'apex' if args.fpaa_backend == 'apex' else 'amp'
         else:
             UpperCamelCase				:   int          =							None
  
         if args.save_on_each_node:
             # deepspeed uses shared storage by default. Let's override this setting if save_on_each_node == True
             UpperCamelCase				:   Union[str, Any]          =							self.config.get("""checkpoint"""    ,      {} )
             UpperCamelCase				:   Tuple          =							args.save_on_each_node
  
         # amp: similar to the pytorch native amp - it has a bunch of optional params but we won't set
         # any here unless the user did the work
         self.fill_match(
             """fp16.enabled"""    ,      ((args.fpaa or args.fpaa_full_eval) and fpaa_backend == """amp""")    ,      """fp16|fp16_full_eval+fp16_backend(amp)"""    ,      )
  
         # apex: delegates amp work to apex (which needs to be available), but it cannot be used with any
         # ZeRO features
         self.fill_match("""amp.enabled"""    ,      fpaa_backend == """apex"""    ,      """fp16+fp16_backend(apex)""" )
         self.fill_match("""amp.opt_level"""    ,      args.fpaa_opt_level    ,      """fp16_opt_level""" )
  
         self.fill_match("""bf16.enabled"""    ,      (args.bfaa or args.bfaa_full_eval)    ,      """bf16|bf16_full_eval""" )
  
         # deepspeed's default mode is fp16 unless there is a config that says differently
         if self.is_true("""bf16.enabled""" ):
             UpperCamelCase				:   Optional[int]          =							torch.bfloataa
         elif self.is_false("""fp16.enabled""" ):
             UpperCamelCase				:   Optional[int]          =							torch.floataa
         else:
             UpperCamelCase				:   Optional[int]          =							torch.floataa
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_ ):
         UpperCamelCase				:   Any          =							[
             'zero_optimization.reduce_bucket_size',
             'zero_optimization.stage3_prefetch_bucket_size',
             'zero_optimization.stage3_param_persistence_threshold',
         ]
         UpperCamelCase				:   Dict          =							[x for x in hidden_size_based_keys if self.is_auto(_A )]
  
         if len(_A ) > 0:
             if hasattr(model.config    ,      """hidden_size""" ):
                 UpperCamelCase				:   Any          =							model.config.hidden_size
             elif hasattr(model.config    ,      """hidden_sizes""" ):
                 # if there are many hidden sizes pick the largest one
                 UpperCamelCase				:   Dict          =							max(model.config.hidden_sizes )
             else:
                 raise ValueError(
                     """The model\'s config file has neither `hidden_size` nor `hidden_sizes` entry, """
                     """therefore it\'s not possible to automatically fill out the following `auto` entries """
                     f'in the DeepSpeed config file: {hidden_size_auto_keys}. You can fix that by replacing '
                     """`auto` values for these keys with an integer value of your choice.""" )
  
             self.fill_only("""zero_optimization.reduce_bucket_size"""    ,      hidden_size * hidden_size )
             if self.is_zeroa():
                 # automatically assign the optimal config values based on model config
                 self.fill_only("""zero_optimization.stage3_prefetch_bucket_size"""    ,      0.9 * hidden_size * hidden_size )
                 self.fill_only("""zero_optimization.stage3_param_persistence_threshold"""    ,      10 * hidden_size )
  
          # scheduler
         self.fill_match("""scheduler.params.total_num_steps"""    ,      _A    ,      """num_training_steps (calculated)""" )
         self.fill_match("""scheduler.params.warmup_num_steps"""    ,      args.get_warmup_steps(_A )    ,      """warmup_steps""" )
  
         if len(self.mismatches ) > 0:
             UpperCamelCase				:   str          =							'\n'.join(self.mismatches )
             raise ValueError(
                 """Please correct the following DeepSpeed config values that mismatch TrainingArguments"""
                 f' values:\n{mismatches}\nThe easiest method is to set these DeepSpeed config values to \'auto\'.' )
  
  
  
  
  
  
  
  __A :		Optional[Any]      							=    None
  def 					A_			(		snake_case_     :       List[Any]    ):
  
  
  
  
  
  
  
      '''simple docstring'''
      global _hf_deepspeed_config_weak_ref
      # will go away automatically when HfDeepSpeedConfig is destroyed (when TrainingArguments is destroyed)
      UpperCamelCase				:   int          =							weakref.ref(snake_case_    )
  def 					A_			(		):
  
  
  
  
  
  
  
      '''simple docstring'''
      global _hf_deepspeed_config_weak_ref
      UpperCamelCase				:   Optional[Any]          =							None
  def 					A_			(		):
  
  
  
  
  
  
  
      '''simple docstring'''
  
  
  
  
  
  
  
      if _hf_deepspeed_config_weak_ref is not None and _hf_deepspeed_config_weak_ref() is not None:
          return _hf_deepspeed_config_weak_ref().is_zeroa()
      else:
          return False
  def 					A_			(		):
  
  
  
  
  
  
  
      '''simple docstring'''
  
  
  
  
  
  
  
      if _hf_deepspeed_config_weak_ref is not None and _hf_deepspeed_config_weak_ref() is not None:
          return _hf_deepspeed_config_weak_ref().config
      else:
          return None
  def 					A_			(		snake_case_     :       Optional[int]						,snake_case_     :       str						,snake_case_     :       Optional[Any]						,snake_case_     :       Optional[Any]						,snake_case_     :       str    ):
  
  
  
  
  
  
  
      '''simple docstring'''
      from accelerate.utils import DummyOptim, DummyScheduler
  
      UpperCamelCase				:   Dict          =							hf_deepspeed_config.config
  
      # Optimizer + Scheduler
      # Currently supported combos:
      # 1. DS scheduler + DS optimizer: Yes
      # 2. HF scheduler + HF optimizer: Yes
      # 3. DS scheduler + HF optimizer: Yes
      # 4. HF scheduler + DS optimizer: No
      #
      # Unless Offload is enabled in which case it's:
      # 1. DS scheduler + DS optimizer: Yes
      # 2. HF scheduler + HF optimizer: Mostly*
      # 3. DS scheduler + HF optimizer: Mostly*
      # 4. HF scheduler + DS optimizer: No
      #
      # Mostly*: All non-native DeepSpeed optimizers that have both CPU and GPU implementation should work (except LAMB)
  
      UpperCamelCase				:   List[str]          =							None
      if "optimizer" in config:
          if args.adafactor:
              raise ValueError(
                  """--adafactor was passed, but also found `optimizer` configured in the DeepSpeed config. """
                  """Only one optimizer can be configured."""    )
          UpperCamelCase				:   Optional[int]          =							DummyOptim(params=snake_case_    )
      else:
          if hf_deepspeed_config.is_offload():
              logger.info(
                  """Detected ZeRO Offload and non-DeepSpeed optimizers: This combination should work as long as the"""
                  """ custom optimizer has both CPU and GPU implementation (except LAMB)"""    )
  
          # ds supports Adam, OneBitAdam, and Lamb optimizers and can import other optimizers from torch.
          # But trainer uses AdamW by default.
          UpperCamelCase				:   Union[str, Any]          =							trainer.create_optimizer()
          # To use other optimizers requires voiding warranty with: `zero_allow_untested_optimizer`
          UpperCamelCase				:   List[Any]          =							True
  
      UpperCamelCase				:   Optional[int]          =							None
      if "scheduler" in config:
          UpperCamelCase				:   str          =							DummyScheduler(snake_case_    )
      else:
          if isinstance(snake_case_						,snake_case_    ):
              raise ValueError(
                  """Found `optimizer` configured in the DeepSpeed config, but no `scheduler`. """
                  """Please configure a scheduler in the DeepSpeed config."""    )
          UpperCamelCase				:   Optional[int]          =							trainer.create_scheduler(num_training_steps=snake_case_						,optimizer=snake_case_    )
  
      return optimizer, lr_scheduler
  def 					A_			(		snake_case_     :       List[str]						,snake_case_     :       Optional[Any]						,snake_case_     :       Dict=False    ):
  
  
  
  
  
  
  
      '''simple docstring'''
      from deepspeed.utils import logger as ds_logger
  
      UpperCamelCase				:   Union[str, Any]          =							trainer.model
      UpperCamelCase				:   Dict          =							trainer.args
  
      UpperCamelCase				:   List[Any]          =							trainer.accelerator.state.deepspeed_plugin.hf_ds_config
  
      # resume config update - some bits like `model` and `num_training_steps` only become available during train
      hf_deepspeed_config.trainer_config_finalize(snake_case_						,snake_case_						,snake_case_    )
  
      # set the Deepspeed log level consistent with the Trainer
      ds_logger.setLevel(args.get_process_log_level()    )
  
      if inference:
          # only Z3 makes sense for the inference
          if not hf_deepspeed_config.is_zeroa():
              raise ValueError("""ZeRO inference only makes sense with ZeRO Stage 3 - please adjust your config"""    )
  
          # in case the training config is re-used for inference
          hf_deepspeed_config.del_config_sub_tree("""optimizer"""    )
          hf_deepspeed_config.del_config_sub_tree("""lr_scheduler"""    )
          UpperCamelCase				:   str          =							None, None
          UpperCamelCase				:   List[Any]          =							None
      else:
          UpperCamelCase				:   List[Any]          =							None  # important for when deepspeed_init is used as re-init
          UpperCamelCase				:   Tuple          =							list(filter(lambda snake_case_    : p.requires_grad						,model.parameters()    )    )
          UpperCamelCase				:   Dict          =							deepspeed_optim_sched(
              snake_case_						,snake_case_						,snake_case_						,snake_case_						,snake_case_    )
  
      # keep for quick debug:
      # from pprint import pprint; pprint(config)
  
      return optimizer, lr_scheduler
  
  
  def 					A_			(		snake_case_     :       List[Any]						,snake_case_     :       Optional[Any]    ):
  
  
  
  
  
  
  
      '''simple docstring'''
      import glob
  
      UpperCamelCase				:   List[Any]          =							sorted(glob.glob(f'{checkpoint_path}/global_step*'    )    )
  
      if len(snake_case_    ) > 0:
          logger.info(f'Attempting to resume from {checkpoint_path}'    )
          # this magically updates self.optimizer and self.lr_scheduler
          UpperCamelCase				:   List[Any]          =							deepspeed_engine.load_checkpoint(
              snake_case_						,load_optimizer_states=snake_case_						,load_lr_scheduler_states=snake_case_    )
          if load_path is None:
              raise ValueError(f'[deepspeed] failed to resume from checkpoint {checkpoint_path}'    )
      else:
          raise ValueError(f'Can\'t find a valid checkpoint at {checkpoint_path}'    )
  
  
  
  
  
style_context: 
  
  
  
  
  """simple docstring"""
  
  
  
  
  import math
  import sys
  class 							lowerCamelCase		:
  
  
  
  
  
  
  
     def __init__(							self ):
         UpperCamelCase				:   Tuple          =							0
         UpperCamelCase				:   Optional[int]          =							[]
         UpperCamelCase				:   Optional[int]          =							{}  # To store the pos of node in array
  
  
  
  
  
  
  
     def       a_							(							self ):
         return self.cur_size == 0
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_ ):
         UpperCamelCase				:   List[str]          =							self.left(SCREAMING_SNAKE_CASE_ )
         UpperCamelCase				:   Optional[int]          =							self.right(SCREAMING_SNAKE_CASE_ )
         if lc < self.cur_size and self.array(SCREAMING_SNAKE_CASE_ )[0] < self.array(SCREAMING_SNAKE_CASE_ )[0]:
             UpperCamelCase				:   str          =							lc
         else:
             UpperCamelCase				:   Union[str, Any]          =							idx
         if rc < self.cur_size and self.array(SCREAMING_SNAKE_CASE_ )[0] < self.array(SCREAMING_SNAKE_CASE_ )[0]:
             UpperCamelCase				:   Optional[Any]          =							rc
         if smallest != idx:
             self.swap(SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_ )
             self.min_heapify(SCREAMING_SNAKE_CASE_ )
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_ ):
         # Inserts a node into the Priority Queue
         UpperCamelCase				:   List[Any]          =							self.cur_size
         self.cur_size += 1
         self.array.append((sys.maxsize, tup[1]) )
         self.decrease_key((sys.maxsize, tup[1])    ,      tup[0] )
  
  
  
  
  
  
  
     def       a_							(							self ):
         # Removes and returns the min element at top of priority queue
         UpperCamelCase				:   str          =							self.array[0][1]
         UpperCamelCase				:   Optional[int]          =							self.array[self.cur_size - 1]
         self.cur_size -= 1
         self.min_heapify(1 )
         del self.pos[min_node]
         return min_node
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_ ):
         # returns the index of left child
         return 2 * i + 1
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_ ):
         # returns the index of right child
         return 2 * i + 2
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_ ):
         # returns the index of parent
         return math.floor(i / 2 )
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_ ):
         # swaps array elements at indices i and j
         # update the pos{}
         UpperCamelCase				:   Dict          =							j
         UpperCamelCase				:   List[str]          =							i
         UpperCamelCase				:   Optional[int]          =							self.array[i]
         UpperCamelCase				:   Union[str, Any]          =							self.array[j]
         UpperCamelCase				:   Optional[int]          =							temp
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_ ):
         UpperCamelCase				:   Tuple          =							self.pos[tup[1]]
         # assuming the new_d is atmost old_d
         UpperCamelCase				:   Union[str, Any]          =							(new_d, tup[1])
         while idx > 0 and self.array[self.par(SCREAMING_SNAKE_CASE_ )][0] > self.array[idx][0]:
             self.swap(SCREAMING_SNAKE_CASE_    ,      self.par(SCREAMING_SNAKE_CASE_ ) )
             UpperCamelCase				:   Union[str, Any]          =							self.par(SCREAMING_SNAKE_CASE_ )
  
  
  
  
  
  
  
  class 							lowerCamelCase		:
  
  
  
  
  
  
  
     def __init__(							self    ,      SCREAMING_SNAKE_CASE_ ):
         UpperCamelCase				:   Any          =							{}  # To store graph: u -> (v,w)
         UpperCamelCase				:   int          =							num  # Number of nodes in graph
         # To store the distance from source vertex
         UpperCamelCase				:   Any          =							[0] * self.num_nodes
         UpperCamelCase				:   Union[str, Any]          =							[-1] * self.num_nodes  # To store the path
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_ ):
         #  Edge going from node u to v and v to u with weight w
         # u (w)-> v, v (w) -> u
         # Check if u already in graph
         if u in self.adjList:
             self.adjList[u].append((v, w) )
         else:
             UpperCamelCase				:   Optional[int]          =							[(v, w)]
  
         # Assuming undirected graph
         if v in self.adjList:
             self.adjList[v].append((u, w) )
         else:
             UpperCamelCase				:   List[Any]          =							[(u, w)]
  
  
  
  
  
  
  
     def       a_							(							self ):
         # u -> v(w)
         for u in self.adjList:
             print(SCREAMING_SNAKE_CASE_    ,      """->"""    ,      """ -> """.join(str(f'{v}({w})' ) for v, w in self.adjList[u] ) )
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_ ):
         # Flush old junk values in par[]
         UpperCamelCase				:   Tuple          =							[-1] * self.num_nodes
         # src is the source node
         UpperCamelCase				:   Dict          =							0
         UpperCamelCase				:   int          =							PriorityQueue()
         q.insert((0, src) )  # (dist from src, node)
         for u in self.adjList:
             if u != src:
                 UpperCamelCase				:   Any          =							sys.maxsize  # Infinity
                 UpperCamelCase				:   int          =							-1
  
         while not q.is_empty():
             UpperCamelCase				:   int          =							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]:
                 UpperCamelCase				:   List[Any]          =							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)    ,      SCREAMING_SNAKE_CASE_ )
                     UpperCamelCase				:   Any          =							new_dist
                     UpperCamelCase				:   Tuple          =							u
  
          # Show the shortest distances from src
         self.show_distances(SCREAMING_SNAKE_CASE_ )
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_ ):
         print(f'Distance from node: {src}' )
         for u in range(self.num_nodes ):
             print(f'Node {u} has distance: {self.dist[u]}' )
  
  
  
  
  
  
  
     def       a_							(							self    ,      SCREAMING_SNAKE_CASE_    ,      SCREAMING_SNAKE_CASE_ ):
         # To show the shortest path from src to dest
         # WARNING: Use it *after* calling dijkstra
         UpperCamelCase				:   Tuple          =							[]
         UpperCamelCase				:   Optional[Any]          =							0
         UpperCamelCase				:   int          =							dest
         # Backtracking from dest to src
         while self.par[temp] != -1:
             path.append(SCREAMING_SNAKE_CASE_ )
             if temp != src:
                 for v, w in self.adjList[temp]:
                     if v == self.par[temp]:
                         cost += w
                         break
             UpperCamelCase				:   int          =							self.par[temp]
         path.append(SCREAMING_SNAKE_CASE_ )
         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: """    ,      SCREAMING_SNAKE_CASE_ )
  
  
  if __name__ == "__main__":
    __A :		int      							=    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, 11)
    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, 14)
    graph.add_edge(4, 5, 10)
    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
  
  
  
  
  