
"""simple docstring"""

import logging
import pathlib
import re
import sys
from dataclasses import dataclass, field
from typing import Any, Callable, Dict, List, Optional, Set, Union

import datasets
import librosa
import numpy as np
import torch
from lang_trans import arabic
from packaging import version
from torch import nn

from transformers import (
    HfArgumentParser,
    Trainer,
    TrainingArguments,
    WavaVecaCTCTokenizer,
    WavaVecaFeatureExtractor,
    WavaVecaForCTC,
    WavaVecaProcessor,
    is_apex_available,
    trainer_utils,
)


if is_apex_available():
   from apex import amp

if version.parse(version.parse(torch.__version__).base_version) >= version.parse('''1.6'''):
   SCREAMING_SNAKE_CASE_         =  True
   from torch.cuda.amp import autocast


SCREAMING_SNAKE_CASE_         =  logging.getLogger(__name__)
@dataclass
class        _UpperCAmelCase							:
      __SCREAMING_SNAKE_CASE				:							str							 =		field(
          metadata={"help": "Path to pretrained model or model identifier from huggingface.co/models"}							)
      __SCREAMING_SNAKE_CASE				:							Optional[str]							 =		field(
          default=SCREAMING_SNAKE_CASE_       ,     metadata={"help": "Where do you want to store the pretrained models downloaded from huggingface.co"}       ,     )
      __SCREAMING_SNAKE_CASE				:							Optional[bool]							 =		field(
          default=SCREAMING_SNAKE_CASE_       ,     metadata={"help": "Whether to freeze the feature extractor layers of the model."}							)
      __SCREAMING_SNAKE_CASE				:							Optional[bool]							 =		field(
          default=SCREAMING_SNAKE_CASE_       ,     metadata={"help": "Whether to log verbose messages or not."}       ,     )




def       lowercase__  (   lowerCAmelCase			:   ModelArguments	,			lowerCAmelCase			:   TrainingArguments	)	-> Any:






    """simple docstring"""




    logging.basicConfig(
        format='%(asctime)s - %(levelname)s - %(name)s - %(message)s'	,			datefmt='%m/%d/%Y %H:%M:%S'	,			handlers=[logging.StreamHandler(sys.stdout	)]	,			)
    UpperCAmelCase       =   logging.WARNING
    if model_args.verbose_logging:
        UpperCAmelCase       =   logging.DEBUG
    elif trainer_utils.is_main_process(training_args.local_rank	):
        UpperCAmelCase       =   logging.INFO
    logger.setLevel(lowerCAmelCase	)
@dataclass
class        _UpperCAmelCase							:
      __SCREAMING_SNAKE_CASE				:							str							 =		field(
          default=SCREAMING_SNAKE_CASE_       ,     metadata={"help": "The name of the dataset to use (via the datasets library)."}							)
      __SCREAMING_SNAKE_CASE				:							Optional[str]							 =		field(
          default=SCREAMING_SNAKE_CASE_       ,     metadata={"help": "The configuration name of the dataset to use (via the datasets library)."}							)
      __SCREAMING_SNAKE_CASE				:							Optional[str]							 =		field(
          default="train"       ,     metadata={
              "help": "The name of the training data set split to use (via the datasets library). Defaults to 'train'"
          }       ,     )
      __SCREAMING_SNAKE_CASE				:							Optional[str]							 =		field(
          default="validation"       ,     metadata={
              "help": (
                  "The name of the validation data set split to use (via the datasets library). Defaults to 'validation'"
              )
          }       ,     )
      __SCREAMING_SNAKE_CASE				:							Optional[str]							 =		field(
          default="text"       ,     metadata={"help": "Column in the dataset that contains label (target text). Defaults to 'text'"}       ,     )
      __SCREAMING_SNAKE_CASE				:							Optional[str]							 =		field(
          default="file"       ,     metadata={"help": "Column in the dataset that contains speech file path. Defaults to 'file'"}       ,     )
      __SCREAMING_SNAKE_CASE				:							Optional[bool]							 =		field(
          default=SCREAMING_SNAKE_CASE_       ,     metadata={"help": "Resample loaded audio to target feature extractor's sampling rate or not."}       ,     )
      __SCREAMING_SNAKE_CASE				:							Optional[float]							 =		field(
          default=SCREAMING_SNAKE_CASE_       ,     metadata={"help": "Filters out examples longer than specified. Defaults to no filtering."}       ,     )
      __SCREAMING_SNAKE_CASE				:							Optional[str]							 =		field(
          default="librispeech"       ,     metadata={
              "help": (
                  "Orthography used for normalization and tokenization: 'librispeech' (default), 'timit', or"
                  " 'buckwalter'."
              )
          }       ,     )
      __SCREAMING_SNAKE_CASE				:							bool							 =		field(
          default=SCREAMING_SNAKE_CASE_       ,     metadata={"help": "Overwrite the cached preprocessed datasets or not."}							)
      __SCREAMING_SNAKE_CASE				:							Optional[int]							 =		field(
          default=SCREAMING_SNAKE_CASE_       ,     metadata={"help": "The number of processes to use for the preprocessing."}       ,     )

@dataclass
class        _UpperCAmelCase							:
      __SCREAMING_SNAKE_CASE				:							bool							 =		False
      __SCREAMING_SNAKE_CASE				:							Optional[str]							 =		None
      __SCREAMING_SNAKE_CASE				:							Optional[str]							 =		"|"
      __SCREAMING_SNAKE_CASE				:							Optional[Dict[str, str]]							 =		field(default_factory=SCREAMING_SNAKE_CASE_							)
      __SCREAMING_SNAKE_CASE				:							Optional[Set[str]]							 =		field(default_factory=SCREAMING_SNAKE_CASE_							)
      __SCREAMING_SNAKE_CASE				:							Optional[Callable[[str], str]]							 =		None




      @classmethod
      def       a_ (							cls				,    lowercase_							)  ->   Tuple:
          if name == "librispeech":
              return cls()
          if name == "timit":
              return cls(
                  do_lower_case=lowercase_				,    translation_table=str.maketrans({'-': ' '}							)				,    )
          if name == "buckwalter":
              UpperCAmelCase       =   {
                  '-': ' ',  # sometimes used to represent pauses
                  '^': 'v',  # fixing "tha" in arabic_speech_corpus dataset
              }
              return cls(
                  vocab_file=pathlib.Path(lowercase_							).parent.joinpath('vocab/buckwalter.json'							)				,    word_delimiter_token='/'				,    translation_table=str.maketrans(lowercase_							)				,    words_to_remove={'sil'}				,    untransliterator=arabic.buckwalter.untransliterate				,    )
          raise ValueError(F"Unsupported orthography: '{name}'."							)




      def       a_ (							self				,    lowercase_							)  ->   str:
          # TODO(elgeish) return a pipeline (e.g., from jiwer) instead? Or rely on branch predictor as is
          if len(self.translation_table							) > 0:
              UpperCAmelCase       =   text.translate(self.translation_table							)
          if len(self.words_to_remove							) == 0:
              UpperCAmelCase       =   ' '.join(text.split()							)  # clean up whitespaces
          else:
              UpperCAmelCase       =   ' '.join(w for w in text.split() if w not in self.words_to_remove							)  # and clean up whilespaces
          return text




      def       a_ (							self				,    lowercase_							)  ->   WavaVecaProcessor:
          UpperCAmelCase       =   WavaVecaFeatureExtractor.from_pretrained(
              model_args.model_name_or_path				,    cache_dir=model_args.cache_dir							)
          if self.vocab_file:
              UpperCAmelCase       =   WavaVecaCTCTokenizer(
                  self.vocab_file				,    cache_dir=model_args.cache_dir				,    do_lower_case=self.do_lower_case				,    word_delimiter_token=self.word_delimiter_token				,    )
          else:
              UpperCAmelCase       =   WavaVecaCTCTokenizer.from_pretrained(
                  model_args.model_name_or_path				,    cache_dir=model_args.cache_dir				,    do_lower_case=self.do_lower_case				,    word_delimiter_token=self.word_delimiter_token				,    )
          return WavaVecaProcessor(lowercase_				,    lowercase_							)

@dataclass
class        _UpperCAmelCase							:
      __SCREAMING_SNAKE_CASE				:							WavaVecaProcessor
      __SCREAMING_SNAKE_CASE				:							Union[bool, str]							 =		True
      __SCREAMING_SNAKE_CASE				:							Optional[int]							 =		None
      __SCREAMING_SNAKE_CASE				:							Optional[int]							 =		None
      __SCREAMING_SNAKE_CASE				:							Optional[int]							 =		None
      __SCREAMING_SNAKE_CASE				:							Optional[int]							 =		None




      def __call__(							self				,    lowercase_							)  ->   Dict[str, torch.Tensor]:
          # split inputs and labels since they have to be of different lenghts and need
          # different padding methods
          UpperCAmelCase       =   [{'input_values': feature['input_values']} for feature in features]
          UpperCAmelCase       =   [{'input_ids': feature['labels']} for feature in features]

          UpperCAmelCase       =   self.processor.pad(
              lowercase_				,    padding=self.padding				,    max_length=self.max_length				,    pad_to_multiple_of=self.pad_to_multiple_of				,    return_tensors='pt'				,    )
          UpperCAmelCase       =   self.processor.pad(
              labels=lowercase_				,    padding=self.padding				,    max_length=self.max_length_labels				,    pad_to_multiple_of=self.pad_to_multiple_of_labels				,    return_tensors='pt'				,    )

          # replace padding with -100 to ignore loss correctly
          UpperCAmelCase       =   labels_batch['input_ids'].masked_fill(labels_batch.attention_mask.ne(1							)				,    -1_0_0							)

          UpperCAmelCase       =   labels

          return batch

class        _UpperCAmelCase							(						SCREAMING_SNAKE_CASE_							):




      def       a_ (							self				,    lowercase_				,    lowercase_							)  ->   torch.Tensor:
          model.train()
          UpperCAmelCase       =   self._prepare_inputs(lowercase_							)

          if self.use_amp:
              with autocast():
                  UpperCAmelCase       =   self.compute_loss(lowercase_				,    lowercase_							)
          else:
              UpperCAmelCase       =   self.compute_loss(lowercase_				,    lowercase_							)

          if self.args.n_gpu > 1:
              if model.module.config.ctc_loss_reduction == "mean":
                  UpperCAmelCase       =   loss.mean()
              elif model.module.config.ctc_loss_reduction == "sum":
                  UpperCAmelCase       =   loss.sum() / (inputs['labels'] >= 0).sum()
              else:
                  raise ValueError(F"{model.config.ctc_loss_reduction} is not valid. Choose one of ['mean', 'sum']"							)

          if self.args.gradient_accumulation_steps > 1:
              UpperCAmelCase       =   loss / self.args.gradient_accumulation_steps

          if self.use_amp:
              self.scaler.scale(lowercase_							).backward()
          elif self.use_apex:
              with amp.scale_loss(lowercase_				,    self.optimizer							) as scaled_loss:
                  scaled_loss.backward()
          elif self.deepspeed:
              self.deepspeed.backward(lowercase_							)
          else:
              loss.backward()

          return loss.detach()




def       lowercase__  (   )	-> Optional[int]:






    """simple docstring"""




    UpperCAmelCase       =   HfArgumentParser((ModelArguments, DataTrainingArguments, TrainingArguments)	)

    UpperCAmelCase     ,							UpperCAmelCase     ,							UpperCAmelCase       =   parser.parse_args_into_dataclasses()
    configure_logger(lowerCAmelCase	,			lowerCAmelCase	)

    UpperCAmelCase       =   Orthography.from_name(data_args.orthography.lower()	)
    UpperCAmelCase       =   orthography.create_processor(lowerCAmelCase	)
    UpperCAmelCase       =   WavaVecaForCTC.from_pretrained(
        model_args.model_name_or_path	,			cache_dir=model_args.cache_dir	,			gradient_checkpointing=training_args.gradient_checkpointing	,			vocab_size=len(processor.tokenizer	)	,			)

    UpperCAmelCase       =   datasets.load_dataset(
        data_args.dataset_name	,			data_args.dataset_config_name	,			split=data_args.train_split_name	)
    UpperCAmelCase       =   datasets.load_dataset(
        data_args.dataset_name	,			data_args.dataset_config_name	,			split=data_args.validation_split_name	)

    UpperCAmelCase       =   datasets.load_metric('wer'	)
    UpperCAmelCase       =   processor.feature_extractor.sampling_rate if data_args.target_feature_extractor_sampling_rate else None
    UpperCAmelCase       =   ''.join(t for t in processor.tokenizer.get_vocab().keys() if len(lowerCAmelCase	) == 1	)
    UpperCAmelCase       =   re.compile(  # remove characters not in vocabulary
        rF"[^\s{re.escape(lowerCAmelCase	)}]"	,			flags=re.IGNORECASE if processor.tokenizer.do_lower_case else 0	,			)
    UpperCAmelCase       =   []

    def prepare_example(lowerCAmelCase			:   Optional[int]	):  # TODO(elgeish) make use of multiprocessing?
        UpperCAmelCase     ,							UpperCAmelCase       =   librosa.load(example[data_args.speech_file_column]	,			sr=lowerCAmelCase	)
        if data_args.max_duration_in_seconds is not None:
            UpperCAmelCase       =   len(example['speech']	) / example['sampling_rate']
        # Normalize and clean up text; order matters!
        UpperCAmelCase       =   orthography.preprocess_for_training(example[data_args.target_text_column]	)
        UpperCAmelCase       =   vocabulary_text_cleaner.sub(''	,			lowerCAmelCase	)
        if updated_text != example[data_args.target_text_column]:
            text_updates.append((example[data_args.target_text_column], updated_text)	)
            UpperCAmelCase       =   updated_text
        return example

    UpperCAmelCase       =   train_dataset.map(lowerCAmelCase	,			remove_columns=[data_args.speech_file_column]	)
    UpperCAmelCase       =   val_dataset.map(lowerCAmelCase	,			remove_columns=[data_args.speech_file_column]	)

    if data_args.max_duration_in_seconds is not None:

        def filter_by_max_duration(lowerCAmelCase			:   Dict	):
            return example["duration_in_seconds"] <= data_args.max_duration_in_seconds

        UpperCAmelCase       =   len(lowerCAmelCase	)
        UpperCAmelCase       =   len(lowerCAmelCase	)
        UpperCAmelCase       =   train_dataset.filter(lowerCAmelCase	,			remove_columns=['duration_in_seconds']	)
        UpperCAmelCase       =   val_dataset.filter(lowerCAmelCase	,			remove_columns=['duration_in_seconds']	)
        if len(lowerCAmelCase	) > old_train_size:
            logger.warning(
                F"Filtered out {len(lowerCAmelCase	) - old_train_size} train example(s) longer than"
                F" {data_args.max_duration_in_seconds} second(s)."	)
        if len(lowerCAmelCase	) > old_val_size:
            logger.warning(
                F"Filtered out {len(lowerCAmelCase	) - old_val_size} validation example(s) longer than"
                F" {data_args.max_duration_in_seconds} second(s)."	)
    logger.info(F"Split sizes: {len(lowerCAmelCase	)} train and {len(lowerCAmelCase	)} validation."	)

    logger.warning(F"Updated {len(lowerCAmelCase	)} transcript(s) using '{data_args.orthography}' orthography rules."	)
    if logger.isEnabledFor(logging.DEBUG	):
        for original_text, updated_text in text_updates:
            logger.debug(F"Updated text: \"{original_text}\" -> \"{updated_text}\""	)
    UpperCAmelCase       =   None

    def prepare_dataset(lowerCAmelCase			:   Optional[int]	):
        # check that all files have the correct sampling rate
        assert (
            len(set(batch['sampling_rate']	)	) == 1
        ), F"Make sure all inputs have the same sampling rate of {processor.feature_extractor.sampling_rate}."

        UpperCAmelCase       =   processor(
            audio=batch['speech']	,			text=batch[data_args.target_text_column]	,			sampling_rate=batch['sampling_rate'][0]	)
        batch.update(lowerCAmelCase	)
        return batch

    UpperCAmelCase       =   train_dataset.map(
        lowerCAmelCase	,			batch_size=training_args.per_device_train_batch_size	,			batched=lowerCAmelCase	,			num_proc=data_args.preprocessing_num_workers	,			)
    UpperCAmelCase       =   val_dataset.map(
        lowerCAmelCase	,			batch_size=training_args.per_device_train_batch_size	,			batched=lowerCAmelCase	,			num_proc=data_args.preprocessing_num_workers	,			)

    UpperCAmelCase       =   DataCollatorCTCWithPadding(processor=lowerCAmelCase	,			padding=lowerCAmelCase	)

    def compute_metrics(lowerCAmelCase			:   int	):
        UpperCAmelCase       =   pred.predictions
        UpperCAmelCase       =   np.argmax(lowerCAmelCase	,			axis=-1	)

        UpperCAmelCase       =   processor.tokenizer.pad_token_id

        UpperCAmelCase       =   processor.batch_decode(lowerCAmelCase	)
        # we do not want to group tokens when computing the metrics
        UpperCAmelCase       =   processor.batch_decode(pred.label_ids	,			group_tokens=lowerCAmelCase	)
        if logger.isEnabledFor(logging.DEBUG	):
            for reference, predicted in zip(lowerCAmelCase	,			lowerCAmelCase	):
                logger.debug(F"reference: \"{reference}\""	)
                logger.debug(F"predicted: \"{predicted}\""	)
                if orthography.untransliterator is not None:
                    logger.debug(F"reference (untransliterated): \"{orthography.untransliterator(lowerCAmelCase	)}\""	)
                    logger.debug(F"predicted (untransliterated): \"{orthography.untransliterator(lowerCAmelCase	)}\""	)

        UpperCAmelCase       =   wer_metric.compute(predictions=lowerCAmelCase	,			references=lowerCAmelCase	)

        return {"wer": wer}

    if model_args.freeze_feature_extractor:
        model.freeze_feature_extractor()

    UpperCAmelCase       =   CTCTrainer(
        model=lowerCAmelCase	,			data_collator=lowerCAmelCase	,			args=lowerCAmelCase	,			compute_metrics=lowerCAmelCase	,			train_dataset=lowerCAmelCase	,			eval_dataset=lowerCAmelCase	,			tokenizer=processor.feature_extractor	,			)

    trainer.train()


if __name__ == "__main__":
   main()





"""simple docstring"""

import math
import sys
class        _UpperCAmelCase							:




      def __init__(							self							)  ->   List[str]:
          UpperCAmelCase       =   0
          UpperCAmelCase       =   []
          UpperCAmelCase       =   {}  # To store the pos of node in array




      def       a_ (							self							)  ->   Dict:
          return self.cur_size == 0




      def       a_ (							self				,    lowercase_							)  ->   List[str]:
          UpperCAmelCase       =   self.left(lowercase_							)
          UpperCAmelCase       =   self.right(lowercase_							)
          if lc < self.cur_size and self.array(lowercase_							)[0] < self.array(lowercase_							)[0]:
              UpperCAmelCase       =   lc
          else:
              UpperCAmelCase       =   idx
          if rc < self.cur_size and self.array(lowercase_							)[0] < self.array(lowercase_							)[0]:
              UpperCAmelCase       =   rc
          if smallest != idx:
              self.swap(lowercase_				,    lowercase_							)
              self.min_heapify(lowercase_							)




      def       a_ (							self				,    lowercase_							)  ->   List[str]:
          # Inserts a node into the Priority Queue
          UpperCAmelCase       =   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							)  ->   int:
          # Removes and returns the min element at top of priority queue
          UpperCAmelCase       =   self.array[0][1]
          UpperCAmelCase       =   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				,    lowercase_							)  ->   Optional[int]:
          # returns the index of left child
          return 2 * i + 1




      def       a_ (							self				,    lowercase_							)  ->   List[Any]:
          # returns the index of right child
          return 2 * i + 2




      def       a_ (							self				,    lowercase_							)  ->   List[Any]:
          # returns the index of parent
          return math.floor(i / 2							)




      def       a_ (							self				,    lowercase_				,    lowercase_							)  ->   List[Any]:
          # swaps array elements at indices i and j
          # update the pos{}
          UpperCAmelCase       =   j
          UpperCAmelCase       =   i
          UpperCAmelCase       =   self.array[i]
          UpperCAmelCase       =   self.array[j]
          UpperCAmelCase       =   temp




      def       a_ (							self				,    lowercase_				,    lowercase_							)  ->   int:
          UpperCAmelCase       =   self.pos[tup[1]]
          # assuming the new_d is atmost old_d
          UpperCAmelCase       =   (new_d, tup[1])
          while idx > 0 and self.array[self.par(lowercase_							)][0] > self.array[idx][0]:
              self.swap(lowercase_				,    self.par(lowercase_							)							)
              UpperCAmelCase       =   self.par(lowercase_							)

class        _UpperCAmelCase							:




      def __init__(							self				,    lowercase_							)  ->   Union[str, Any]:
          UpperCAmelCase       =   {}  # To store graph: u -> (v,w)
          UpperCAmelCase       =   num  # Number of nodes in graph
          # To store the distance from source vertex
          UpperCAmelCase       =   [0] * self.num_nodes
          UpperCAmelCase       =   [-1] * self.num_nodes  # To store the path




      def       a_ (							self				,    lowercase_				,    lowercase_				,    lowercase_							)  ->   Any:
          #  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       =   [(v, w)]

          # Assuming undirected graph
          if v in self.adjList:
              self.adjList[v].append((u, w)							)
          else:
              UpperCAmelCase       =   [(u, w)]




      def       a_ (							self							)  ->   Optional[Any]:
          # u -> v(w)
          for u in self.adjList:
              print(lowercase_				,    '->'				,    ' -> '.join(str(F"{v}({w})"							) for v, w in self.adjList[u]							)							)




      def       a_ (							self				,    lowercase_							)  ->   int:
          # Flush old junk values in par[]
          UpperCAmelCase       =   [-1] * self.num_nodes
          # src is the source node
          UpperCAmelCase       =   0
          UpperCAmelCase       =   PriorityQueue()
          q.insert((0, src)							)  # (dist from src, node)
          for u in self.adjList:
              if u != src:
                  UpperCAmelCase       =   sys.maxsize  # Infinity
                  UpperCAmelCase       =   -1

          while not q.is_empty():
              UpperCAmelCase       =   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       =   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)				,    lowercase_							)
                      UpperCAmelCase       =   new_dist
                      UpperCAmelCase       =   u

        # Show the shortest distances from src
          self.show_distances(lowercase_							)




      def       a_ (							self				,    lowercase_							)  ->   Any:
          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				,    lowercase_				,    lowercase_							)  ->   List[Any]:
          # To show the shortest path from src to dest
          # WARNING: Use it *after* calling dijkstra
          UpperCAmelCase       =   []
          UpperCAmelCase       =   0
          UpperCAmelCase       =   dest
          # Backtracking from dest to src
          while self.par[temp] != -1:
              path.append(lowercase_							)
              if temp != src:
                  for v, w in self.adjList[temp]:
                      if v == self.par[temp]:
                          cost += w
                          break
              UpperCAmelCase       =   self.par[temp]
          path.append(lowercase_							)
          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: '				,    lowercase_							)


if __name__ == "__main__":
   SCREAMING_SNAKE_CASE_         =  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



