




import math
import sys






class       A      :
     """simple docstring"""

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




     def 			__snake_case (     self	: List[Any]      )					->							Dict:
           return self.cur_size == 0




     def 			__snake_case (     self	: Dict						,	A__	: Optional[Any]      )					->							Dict:
           lowerCamelCase__   	=					self.left(A__      )
           lowerCamelCase__   	=					self.right(A__      )
           if lc < self.cur_size and self.array(A__      )[0] < self.array(A__      )[0]:
                 lowerCamelCase__   	=					lc
           else:
                 lowerCamelCase__   	=					idx
           if rc < self.cur_size and self.array(A__      )[0] < self.array(A__      )[0]:
                 lowerCamelCase__   	=					rc
           if smallest != idx:
                 self.swap(A__						,	A__      )
                 self.min_heapify(A__      )




     def 			__snake_case (     self	: Optional[int]						,	A__	: Optional[int]      )					->							Dict:
           # Inserts a node into the Priority Queue
           lowerCamelCase__   	=					self.cur_size
           self.cur_size += 1
           self.array.append((sys.maxsize, tup[1])      )
           self.decrease_key((sys.maxsize, tup[1])						,	tup[0]      )




     def 			__snake_case (     self	: int      )					->							List[Any]:
           # Removes and returns the min element at top of priority queue
           lowerCamelCase__   	=					self.array[0][1]
           lowerCamelCase__   	=					self.array[self.cur_size - 1]
           self.cur_size -= 1
           self.min_heapify(1      )
           del self.pos[min_node]
           return min_node




     def 			__snake_case (     self	: Optional[int]						,	A__	: Tuple      )					->							Optional[int]:
           # returns the index of left child
           return 2 * i + 1




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




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




     def 			__snake_case (     self	: Union[str, Any]						,	A__	: Dict						,	A__	: Any      )					->							Tuple:
           # swaps array elements at indices i and j
           # update the pos{}
           lowerCamelCase__   	=					j
           lowerCamelCase__   	=					i
           lowerCamelCase__   	=					self.array[i]
           lowerCamelCase__   	=					self.array[j]
           lowerCamelCase__   	=					temp




     def 			__snake_case (     self	: Tuple						,	A__	: Any						,	A__	: str      )					->							Dict:
           lowerCamelCase__   	=					self.pos[tup[1]]
           # assuming the new_d is atmost old_d
           lowerCamelCase__   	=					(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__   	=					self.par(A__      )






class       A      :
     """simple docstring"""

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




     def 			__snake_case (     self	: List[Any]						,	A__	: Dict						,	A__	: Any						,	A__	: int      )					->							str:
           #  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:
                 lowerCamelCase__   	=					[(v, w)]

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




     def 			__snake_case (     self	: Tuple      )					->							Optional[int]:
           # u -> v(w)
           for u in self.adjList:
                 print(A__						,	'->'						,	' -> '.join(str(F"""{v}({w})"""      ) for v, w in self.adjList[u]      )      )




     def 			__snake_case (     self	: Optional[Any]						,	A__	: List[str]      )					->							List[str]:
           # Flush old junk values in par[]
           lowerCamelCase__   	=					[-1] * self.num_nodes
           # src is the source node
           lowerCamelCase__   	=					0
           lowerCamelCase__   	=					PriorityQueue()
           q.insert((0, src)      )  # (dist from src, node)
           for u in self.adjList:
                 if u != src:
                       lowerCamelCase__   	=					sys.maxsize  # Infinity
                       lowerCamelCase__   	=					-1

           while not q.is_empty():
                 lowerCamelCase__   	=					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__   	=					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__   	=					new_dist
                             lowerCamelCase__   	=					u

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




     def 			__snake_case (     self	: Optional[int]						,	A__	: Optional[Any]      )					->							Dict:
           print(F"""Distance from node: {src}"""      )
           for u in range(self.num_nodes      ):
                 print(F"""Node {u} has distance: {self.dist[u]}"""      )




     def 			__snake_case (     self	: List[Any]						,	A__	: Any						,	A__	: Tuple      )					->							str:
           # To show the shortest path from src to dest
           # WARNING: Use it *after* calling dijkstra
           lowerCamelCase__   	=					[]
           lowerCamelCase__   	=					0
           lowerCamelCase__   	=					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__   	=					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__":
      __SCREAMING_SNAKE_CASE     : Optional[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





from typing import TYPE_CHECKING

from ...utils import (
    OptionalDependencyNotAvailable,
    _LazyModule,
    is_sentencepiece_available,
    is_tokenizers_available,
    is_torch_available,
)


__SCREAMING_SNAKE_CASE     : Tuple      ={
    """configuration_open_llama""": ["""OPEN_LLAMA_PRETRAINED_CONFIG_ARCHIVE_MAP""", """OpenLlamaConfig"""],
}

try:
      if not is_sentencepiece_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      __SCREAMING_SNAKE_CASE     : Dict      =["""LlamaTokenizer"""]

try:
      if not is_tokenizers_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      __SCREAMING_SNAKE_CASE     : int      =["""LlamaTokenizerFast"""]

try:
      if not is_torch_available():
            raise OptionalDependencyNotAvailable()
except OptionalDependencyNotAvailable:
      pass
else:
      __SCREAMING_SNAKE_CASE     : Optional[Any]      =[
          """OpenLlamaForCausalLM""",
          """OpenLlamaModel""",
          """OpenLlamaPreTrainedModel""",
          """OpenLlamaForSequenceClassification""",
      ]


if TYPE_CHECKING:
      from .configuration_open_llama import OPEN_LLAMA_PRETRAINED_CONFIG_ARCHIVE_MAP, OpenLlamaConfig

      try:
            if not is_sentencepiece_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from transformers import LlamaTokenizer

      try:
            if not is_tokenizers_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from transformers import LlamaTokenizerFast

      try:
            if not is_torch_available():
                  raise OptionalDependencyNotAvailable()
      except OptionalDependencyNotAvailable:
            pass
      else:
            from .modeling_open_llama import (
                OpenLlamaForCausalLM,
                OpenLlamaForSequenceClassification,
                OpenLlamaModel,
                OpenLlamaPreTrainedModel,
            )


else:
      import sys

      __SCREAMING_SNAKE_CASE     : Union[str, Any]      =_LazyModule(__name__, globals()["""__file__"""], _import_structure, module_spec=__spec__)