




import argparse
import logging
import os
from pathlib import Path
from typing import Any, Dict

import pytorch_lightning as pl
from pytorch_lightning.utilities import rank_zero_info

from transformers import (
    AdamW,
    AutoConfig,
    AutoModel,
    AutoModelForPreTraining,
    AutoModelForQuestionAnswering,
    AutoModelForSeqaSeqLM,
    AutoModelForSequenceClassification,
    AutoModelForTokenClassification,
    AutoModelWithLMHead,
    AutoTokenizer,
    PretrainedConfig,
    PreTrainedTokenizer,
)
from transformers.optimization import (
    Adafactor,
    get_cosine_schedule_with_warmup,
    get_cosine_with_hard_restarts_schedule_with_warmup,
    get_linear_schedule_with_warmup,
    get_polynomial_decay_schedule_with_warmup,
)
from transformers.utils.versions import require_version


UpperCamelCase__						=		logging.getLogger(__name__)

require_version('pytorch_lightning>=1.0.4')

UpperCamelCase__						=		{
    'base': AutoModel,
    'sequence-classification': AutoModelForSequenceClassification,
    'question-answering': AutoModelForQuestionAnswering,
    'pretraining': AutoModelForPreTraining,
    'token-classification': AutoModelForTokenClassification,
    'language-modeling': AutoModelWithLMHead,
    'summarization': AutoModelForSeqaSeqLM,
    'translation': AutoModelForSeqaSeqLM,
}


# update this and the import above to support new schedulers from transformers.optimization
UpperCamelCase__						=		{
    'linear': get_linear_schedule_with_warmup,
    'cosine': get_cosine_schedule_with_warmup,
    'cosine_w_restarts': get_cosine_with_hard_restarts_schedule_with_warmup,
    'polynomial': get_polynomial_decay_schedule_with_warmup,
    # '': get_constant_schedule,             # not supported for now
    # '': get_constant_schedule_with_warmup, # not supported for now
}
UpperCamelCase__						=		sorted(arg_to_scheduler.keys())
UpperCamelCase__						=		'{' + ', '.join(arg_to_scheduler_choices) + '}'


class 							__SCREAMING_SNAKE_CASE				(						pl.LightningModule    ):

					def __init__(							self					,			__lowercase					,			__lowercase=None					,			__lowercase="base"					,			__lowercase=None					,			__lowercase=None					,			__lowercase=None					,			**__lowercase					,			):







						'''simple docstring'''




						super().__init__()
						# TODO: move to self.save_hyperparameters()
						# self.save_hyperparameters()
						# can also expand arguments into trainer signature for easier reading

						self.save_hyperparameters(__lowercase   )
						lowerCamelCase_				:						Optional[int]				  =				0
						lowerCamelCase_				:						Dict				  =				Path(self.hparams.output_dir   )
						lowerCamelCase_				:						str				  =				self.hparams.cache_dir if self.hparams.cache_dir else None
						if config is None:
							lowerCamelCase_				:						Optional[int]				  =				AutoConfig.from_pretrained(
							    self.hparams.config_name if self.hparams.config_name else self.hparams.model_name_or_path					,			**({'num_labels': num_labels} if num_labels is not None else {})					,			cache_dir=__lowercase					,			**__lowercase					,			)
						else:
							lowerCamelCase_				:						PretrainedConfig				  =				config

						lowerCamelCase_				:						Dict				  =				('encoder_layerdrop', 'decoder_layerdrop', 'dropout', 'attention_dropout')
						for p in extra_model_params:
							if getattr(self.hparams					,			__lowercase					,			__lowercase   ):
								assert hasattr(self.config					,			__lowercase   ), f"model config doesn't have a `{p}` attribute"
								setattr(self.config					,			__lowercase					,			getattr(self.hparams					,			__lowercase   )   )

						if tokenizer is None:
							lowerCamelCase_				:						Any				  =				AutoTokenizer.from_pretrained(
							    self.hparams.tokenizer_name if self.hparams.tokenizer_name else self.hparams.model_name_or_path					,			cache_dir=__lowercase					,			)
						else:
							lowerCamelCase_				:						PreTrainedTokenizer				  =				tokenizer
						lowerCamelCase_				:						Dict				  =				MODEL_MODES[mode]
						if model is None:
							lowerCamelCase_				:						int				  =				self.model_type.from_pretrained(
							    self.hparams.model_name_or_path					,			from_tf=bool('.ckpt' in self.hparams.model_name_or_path   )					,			config=self.config					,			cache_dir=__lowercase					,			)
						else:
							lowerCamelCase_				:						Optional[int]				  =				model

					def       lowercase_				(							self					,			*__lowercase					,			**__lowercase   ):







						'''simple docstring'''




						lowerCamelCase_				:						Optional[Any]				  =				self.model_type.from_pretrained(*__lowercase					,			**__lowercase   )

					def       lowercase_				(							self   ):







						'''simple docstring'''




						lowerCamelCase_				:						Dict				  =				arg_to_scheduler[self.hparams.lr_scheduler]
						lowerCamelCase_				:						List[str]				  =				get_schedule_func(
						    self.opt					,			num_warmup_steps=self.hparams.warmup_steps					,			num_training_steps=self.total_steps()   )
						lowerCamelCase_				:						Optional[Any]				  =				{'scheduler': scheduler, 'interval': 'step', 'frequency': 1}
						return scheduler

					def       lowercase_				(							self   ):







						'''simple docstring'''




						lowerCamelCase_				:						str				  =				self.model
						lowerCamelCase_				:						List[str]				  =				['bias', 'LayerNorm.weight']
						lowerCamelCase_				:						Optional[int]				  =				[
						    {
						        'params': [p for n, p in model.named_parameters() if not any(nd in n for nd in no_decay   )],
						        'weight_decay': self.hparams.weight_decay,
						    },
						    {
						        'params': [p for n, p in model.named_parameters() if any(nd in n for nd in no_decay   )],
						        'weight_decay': 0.0,
						    },
						]
						if self.hparams.adafactor:
							lowerCamelCase_				:						Dict				  =				Adafactor(
							    __lowercase					,			lr=self.hparams.learning_rate					,			scale_parameter=__lowercase					,			relative_step=__lowercase   )

						else:
							lowerCamelCase_				:						str				  =				AdamW(
							    __lowercase					,			lr=self.hparams.learning_rate					,			eps=self.hparams.adam_epsilon   )
						lowerCamelCase_				:						str				  =				optimizer

						lowerCamelCase_				:						Any				  =				self.get_lr_scheduler()

						return [optimizer], [scheduler]

					def       lowercase_				(							self					,			__lowercase					,			__lowercase   ):







						'''simple docstring'''




						return self.validation_step(__lowercase					,			__lowercase   )

					def       lowercase_				(							self					,			__lowercase   ):







						'''simple docstring'''




						return self.validation_end(__lowercase   )

					def       lowercase_				(							self   ):







						'''simple docstring'''




						lowerCamelCase_				:						Dict				  =				max(1					,			self.hparams.gpus   )  # TODO: consider num_tpu_cores
						lowerCamelCase_				:						Optional[Any]				  =				self.hparams.train_batch_size * self.hparams.accumulate_grad_batches * num_devices
						return (self.dataset_size / effective_batch_size) * self.hparams.max_epochs

					def       lowercase_				(							self					,			__lowercase   ):







						'''simple docstring'''




						if mode == "test":
							lowerCamelCase_				:						List[str]				  =				len(self.test_dataloader().dataset   )
						else:
							lowerCamelCase_				:						Optional[Any]				  =				self.get_dataloader('train'					,			self.hparams.train_batch_size					,			shuffle=__lowercase   )
							lowerCamelCase_				:						Tuple				  =				len(self.train_dataloader().dataset   )

					def       lowercase_				(							self					,			__lowercase					,			__lowercase					,			__lowercase = False   ):







						'''simple docstring'''




						raise NotImplementedError('You must implement this for your task'   )

					def       lowercase_				(							self   ):







						'''simple docstring'''




						return self.train_loader

					def       lowercase_				(							self   ):







						'''simple docstring'''




						return self.get_dataloader('dev'					,			self.hparams.eval_batch_size					,			shuffle=__lowercase   )

					def       lowercase_				(							self   ):







						'''simple docstring'''




						return self.get_dataloader('test'					,			self.hparams.eval_batch_size					,			shuffle=__lowercase   )

					def       lowercase_				(							self					,			__lowercase   ):







						'''simple docstring'''




						return os.path.join(
						    self.hparams.data_dir					,			'cached_{}_{}_{}'.format(
						        __lowercase					,			list(filter(__lowercase					,			self.hparams.model_name_or_path.split('/'   )   )   ).pop()					,			str(self.hparams.max_seq_length   )					,			)					,			)

					@pl.utilities.rank_zero_only
					def       lowercase_				(							self					,			__lowercase   ):







						'''simple docstring'''




						lowerCamelCase_				:						List[str]				  =				self.output_dir.joinpath('best_tfmr'   )
						lowerCamelCase_				:						Dict				  =				self.step_count
						self.model.save_pretrained(__lowercase   )
						self.tokenizer.save_pretrained(__lowercase   )





					@staticmethod
					def       lowercase_				(							__lowercase					,			__lowercase   ):







						'''simple docstring'''




						parser.add_argument(
						    '--model_name_or_path'					,			default=__lowercase					,			type=__lowercase					,			required=__lowercase					,			help='Path to pretrained model or model identifier from huggingface.co/models'					,			)
						parser.add_argument(
						    '--config_name'					,			default=''					,			type=__lowercase					,			help='Pretrained config name or path if not the same as model_name'   )
						parser.add_argument(
						    '--tokenizer_name'					,			default=__lowercase					,			type=__lowercase					,			help='Pretrained tokenizer name or path if not the same as model_name'					,			)
						parser.add_argument(
						    '--cache_dir'					,			default=''					,			type=__lowercase					,			help='Where do you want to store the pre-trained models downloaded from huggingface.co'					,			)
						parser.add_argument(
						    '--encoder_layerdrop'					,			type=__lowercase					,			help='Encoder layer dropout probability (Optional). Goes into model.config'					,			)
						parser.add_argument(
						    '--decoder_layerdrop'					,			type=__lowercase					,			help='Decoder layer dropout probability (Optional). Goes into model.config'					,			)
						parser.add_argument(
						    '--dropout'					,			type=__lowercase					,			help='Dropout probability (Optional). Goes into model.config'					,			)
						parser.add_argument(
						    '--attention_dropout'					,			type=__lowercase					,			help='Attention dropout probability (Optional). Goes into model.config'					,			)
						parser.add_argument('--learning_rate'					,			default=5E-5					,			type=__lowercase					,			help='The initial learning rate for Adam.'   )
						parser.add_argument(
						    '--lr_scheduler'					,			default='linear'					,			choices=__lowercase					,			metavar=__lowercase					,			type=__lowercase					,			help='Learning rate scheduler'					,			)
						parser.add_argument('--weight_decay'					,			default=0.0					,			type=__lowercase					,			help='Weight decay if we apply some.'   )
						parser.add_argument('--adam_epsilon'					,			default=1E-8					,			type=__lowercase					,			help='Epsilon for Adam optimizer.'   )
						parser.add_argument('--warmup_steps'					,			default=0					,			type=__lowercase					,			help='Linear warmup over warmup_steps.'   )
						parser.add_argument('--num_workers'					,			default=4					,			type=__lowercase					,			help='kwarg passed to DataLoader'   )
						parser.add_argument('--num_train_epochs'					,			dest='max_epochs'					,			default=3					,			type=__lowercase   )
						parser.add_argument('--train_batch_size'					,			default=32					,			type=__lowercase   )
						parser.add_argument('--eval_batch_size'					,			default=32					,			type=__lowercase   )
						parser.add_argument('--adafactor'					,			action='store_true'   )


class 							__SCREAMING_SNAKE_CASE				(						pl.Callback    ):

					def       lowercase_				(							self					,			__lowercase					,			__lowercase   ):







						'''simple docstring'''




						lowerCamelCase_				:						Tuple				  =				trainer.lr_schedulers[0]['scheduler']
						lowerCamelCase_				:						str				  =				{f"lr_group_{i}": lr for i, lr in enumerate(lr_scheduler.get_lr()   )}
						pl_module.logger.log_metrics(__lowercase   )

					def       lowercase_				(							self					,			__lowercase					,			__lowercase   ):







						'''simple docstring'''




						rank_zero_info('***** Validation results *****'   )
						lowerCamelCase_				:						Optional[Any]				  =				trainer.callback_metrics
						# Log results
						for key in sorted(__lowercase   ):
							if key not in ["log", "progress_bar"]:
								rank_zero_info('{} = {}\n'.format(__lowercase					,			str(metrics[key]   )   )   )





					def       lowercase_				(							self					,			__lowercase					,			__lowercase   ):







						'''simple docstring'''




						rank_zero_info('***** Test results *****'   )
						lowerCamelCase_				:						Tuple				  =				trainer.callback_metrics
						# Log and save results to file
						lowerCamelCase_				:						Optional[Any]				  =				os.path.join(pl_module.hparams.output_dir					,			'test_results.txt'   )
						with open(__lowercase					,			'w'   ) as writer:
							for key in sorted(__lowercase   ):
								if key not in ["log", "progress_bar"]:
									rank_zero_info('{} = {}\n'.format(__lowercase					,			str(metrics[key]   )   )   )
									writer.write('{} = {}\n'.format(__lowercase					,			str(metrics[key]   )   )   )






def    snake_case   (				A		,  A     )				->				None:




	'''simple docstring'''


	parser.add_argument(
	    '--output_dir'		,  default=A		,  type=A		,  required=A		,  help='The output directory where the model predictions and checkpoints will be written.'		,  )
	parser.add_argument(
	    '--fp16'		,  action='store_true'		,  help='Whether to use 16-bit (mixed) precision (through NVIDIA apex) instead of 32-bit'		,  )

	parser.add_argument(
	    '--fp16_opt_level'		,  type=A		,  default='O2'		,  help=(
	        'For fp16: Apex AMP optimization level selected in [\'O0\', \'O1\', \'O2\', and \'O3\'].'
	        'See details at https://nvidia.github.io/apex/amp.html'
	    )		,  )
	parser.add_argument('--n_tpu_cores'		,  dest='tpu_cores'		,  type=A     )
	parser.add_argument('--max_grad_norm'		,  dest='gradient_clip_val'		,  default=1.0		,  type=A		,  help='Max gradient norm'     )
	parser.add_argument('--do_train'		,  action='store_true'		,  help='Whether to run training.'     )
	parser.add_argument('--do_predict'		,  action='store_true'		,  help='Whether to run predictions on the test set.'     )
	parser.add_argument(
	    '--gradient_accumulation_steps'		,  dest='accumulate_grad_batches'		,  type=A		,  default=1		,  help='Number of updates steps to accumulate before performing a backward/update pass.'		,  )
	parser.add_argument('--seed'		,  type=A		,  default=42		,  help='random seed for initialization'     )
	parser.add_argument(
	    '--data_dir'		,  default=A		,  type=A		,  required=A		,  help='The input data dir. Should contain the training files for the CoNLL-2003 NER task.'		,  )






def    snake_case   (				A		,  A		,  A=None		,  A=True		,  A=[]		,  A=None		,  A=None		,  **A		,  )				->				Optional[Any]:




	'''simple docstring'''


	pl.seed_everything(args.seed     )

	# init model
	lowerCamelCase_				:						Dict				  =				Path(model.hparams.output_dir     )
	odir.mkdir(exist_ok=A     )

	# add custom checkpoints
	if checkpoint_callback is None:
		lowerCamelCase_				:						str				  =				pl.callbacks.ModelCheckpoint(
		    filepath=args.output_dir		,  prefix='checkpoint'		,  monitor='val_loss'		,  mode='min'		,  save_top_k=1     )
	if early_stopping_callback:
		extra_callbacks.append(A     )
	if logging_callback is None:
		lowerCamelCase_				:						Optional[Any]				  =				LoggingCallback()

	lowerCamelCase_				:						Any				  =				{}

	# TODO: remove with PyTorch 1.6 since pl uses native amp
	if args.fpaa:
		lowerCamelCase_				:						List[str]				  =				16
		lowerCamelCase_				:						Optional[int]				  =				args.fpaa_opt_level

	if args.gpus > 1:
		lowerCamelCase_				:						List[Any]				  =				'ddp'

	lowerCamelCase_				:						Dict				  =				args.accumulate_grad_batches
	lowerCamelCase_				:						Any				  =				extra_train_kwargs.get('accelerator'		,  A     )
	lowerCamelCase_				:						Union[str, Any]				  =				extra_train_kwargs.get('profiler'		,  A     )

	lowerCamelCase_				:						str				  =				pl.Trainer.from_argparse_args(
	    A		,  weights_summary=A		,  callbacks=[logging_callback] + extra_callbacks		,  logger=A		,  checkpoint_callback=A		,  **A		,  )

	if args.do_train:
		trainer.fit(A     )

	return trainer




'''simple docstring'''




import math
import sys





class _snake_case :
							"""simple docstring"""





							def __init__( self						)  ->int:



											"""simple docstring"""







											__lowerCamelCase		:   int           =       0
											__lowerCamelCase		:   str           =       []
											__lowerCamelCase		:   int           =       {}  # To store the pos of node in array







							def 		__SCREAMING_SNAKE_CASE( self						)  ->Union[str, Any]:



											"""simple docstring"""







											return self.cur_size == 0







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->Union[str, Any]:



											"""simple docstring"""







											__lowerCamelCase		:   Any           =       self.left(__A						)
											__lowerCamelCase		:   Any           =       self.right(__A						)
											if lc < self.cur_size and self.array(__A						)[0] < self.array(__A						)[0]:
															__lowerCamelCase		:   Dict           =       lc
											else:
															__lowerCamelCase		:   List[Any]           =       idx
											if rc < self.cur_size and self.array(__A						)[0] < self.array(__A						)[0]:
															__lowerCamelCase		:   List[str]           =       rc
											if smallest != idx:
															self.swap(__A      ,					__A						)
															self.min_heapify(__A						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->str:



											"""simple docstring"""







											__lowerCamelCase		:   Optional[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 		__SCREAMING_SNAKE_CASE( self						)  ->int:



											"""simple docstring"""







											__lowerCamelCase		:   Tuple           =       self.array[0][1]
											__lowerCamelCase		:   str           =       self.array[self.cur_size - 1]
											self.cur_size -= 1
											self.min_heapify(1						)
											del self.pos[min_node]
											return min_node







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->int:



											"""simple docstring"""







											return 2 * i + 1







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->Optional[Any]:



											"""simple docstring"""







											return 2 * i + 2







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->Tuple:



											"""simple docstring"""







											return math.floor(i / 2						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A						)  ->List[Any]:



											"""simple docstring"""







											__lowerCamelCase		:   Union[str, Any]           =       j
											__lowerCamelCase		:   str           =       i
											__lowerCamelCase		:   Dict           =       self.array[i]
											__lowerCamelCase		:   Union[str, Any]           =       self.array[j]
											__lowerCamelCase		:   str           =       temp







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A						)  ->Optional[Any]:



											"""simple docstring"""







											__lowerCamelCase		:   str           =       self.pos[tup[1]]
											# assuming the new_d is atmost old_d
											__lowerCamelCase		:   Union[str, Any]           =       (new_d, tup[1])
											while idx > 0 and self.array[self.par(__A						)][0] > self.array[idx][0]:
															self.swap(__A      ,					self.par(__A						)						)
															__lowerCamelCase		:   List[Any]           =       self.par(__A						)





class _snake_case :
							"""simple docstring"""





							def __init__( self      ,					__A						)  ->Any:



											"""simple docstring"""







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







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A      ,					__A						)  ->Optional[Any]:



											"""simple docstring"""







											if u in self.adjList:
															self.adjList[u].append((v, w)						)
											else:
															__lowerCamelCase		:   Dict           =       [(v, w)]

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







							def 		__SCREAMING_SNAKE_CASE( self						)  ->Tuple:



											"""simple docstring"""







											for u in self.adjList:
															print(__A      ,					"->"      ,					" -> ".join(str(f'{v}({w})'						) for v, w in self.adjList[u]						)						)







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->int:



											"""simple docstring"""







											__lowerCamelCase		:   List[str]           =       [-1] * self.num_nodes
											# src is the source node
											__lowerCamelCase		:   str           =       0
											__lowerCamelCase		:   int           =       PriorityQueue()
											q.insert((0, src)						)  # (dist from src, node)
											for u in self.adjList:
															if u != src:
																			__lowerCamelCase		:   List[Any]           =       sys.maxsize  # Infinity
																			__lowerCamelCase		:   Dict           =       -1

											while not q.is_empty():
															__lowerCamelCase		:   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]:
																			__lowerCamelCase		:   str           =       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)      ,					__A						)
																							__lowerCamelCase		:   str           =       new_dist
																							__lowerCamelCase		:   Tuple           =       u

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







							def 		__SCREAMING_SNAKE_CASE( self      ,					__A						)  ->int:



											"""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 		__SCREAMING_SNAKE_CASE( self      ,					__A      ,					__A						)  ->Optional[int]:



											"""simple docstring"""







											__lowerCamelCase		:   List[Any]           =       []
											__lowerCamelCase		:   Tuple           =       0
											__lowerCamelCase		:   List[str]           =       dest
											# Backtracking from dest to src
											while self.par[temp] != -1:
															path.append(__A						)
															if temp != src:
																			for v, w in self.adjList[temp]:
																							if v == self.par[temp]:
																											cost += w
																											break
															__lowerCamelCase		:   int           =       self.par[temp]
											path.append(__A						)
											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: "      ,					__A						)


if __name__ == "__main__":
				__lowercase	:   Optional[Any]   		=					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





