





import math
import sys

class 	__snake_case					:






    '''simple docstring'''





    def __init__( self    :		List[Any]				):

      """simple docstring"""





      __lowerCAmelCase								=					0
      __lowerCAmelCase								=					[]
      __lowerCAmelCase								=					{}  # To store the pos of node in array





    def 						A		( self    :		Tuple				):

      """simple docstring"""





      return self.cur_size == 0





    def 						A		( self    :		Union[str, Any]      ,    snake_case    :		str				):

      """simple docstring"""





      __lowerCAmelCase								=					self.left(snake_case				)
      __lowerCAmelCase								=					self.right(snake_case				)
      if lc < self.cur_size and self.array(snake_case				)[0] < self.array(snake_case				)[0]:
        __lowerCAmelCase								=					lc
      else:
        __lowerCAmelCase								=					idx
      if rc < self.cur_size and self.array(snake_case				)[0] < self.array(snake_case				)[0]:
        __lowerCAmelCase								=					rc
      if smallest != idx:
        self.swap(snake_case      ,    snake_case				)
        self.min_heapify(snake_case				)





    def 						A		( self    :		Optional[int]      ,    snake_case    :		Optional[int]				):

      """simple docstring"""





      __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 						A		( self    :		List[str]				):

      """simple docstring"""





      __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 						A		( self    :		List[Any]      ,    snake_case    :		Any				):

      """simple docstring"""





      return 2 * i + 1





    def 						A		( self    :		Optional[int]      ,    snake_case    :		List[str]				):

      """simple docstring"""





      return 2 * i + 2





    def 						A		( self    :		Union[str, Any]      ,    snake_case    :		str				):

      """simple docstring"""





      return math.floor(i / 2				)





    def 						A		( self    :		Tuple      ,    snake_case    :		str      ,    snake_case    :		List[Any]				):

      """simple docstring"""





      __lowerCAmelCase								=					j
      __lowerCAmelCase								=					i
      __lowerCAmelCase								=					self.array[i]
      __lowerCAmelCase								=					self.array[j]
      __lowerCAmelCase								=					temp





    def 						A		( self    :		Union[str, Any]      ,    snake_case    :		List[str]      ,    snake_case    :		Any				):

      """simple docstring"""





      __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(snake_case				)][0] > self.array[idx][0]:
        self.swap(snake_case      ,    self.par(snake_case				)				)
        __lowerCAmelCase								=					self.par(snake_case				)


class 	__snake_case					:






    '''simple docstring'''





    def __init__( self    :		List[str]      ,    snake_case    :		Union[str, Any]				):

      """simple docstring"""





      __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 						A		( self    :		Tuple      ,    snake_case    :		Union[str, Any]      ,    snake_case    :		Tuple      ,    snake_case    :		Optional[Any]				):

      """simple docstring"""





      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 						A		( self    :		int				):

      """simple docstring"""





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





    def 						A		( self    :		Any      ,    snake_case    :		int				):

      """simple docstring"""





      __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)      ,    snake_case				)
            __lowerCAmelCase								=					new_dist
            __lowerCAmelCase								=					u

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





    def 						A		( self    :		str      ,    snake_case    :		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 						A		( self    :		List[Any]      ,    snake_case    :		int      ,    snake_case    :		List[Any]				):

      """simple docstring"""





      __lowerCAmelCase								=					[]
      __lowerCAmelCase								=					0
      __lowerCAmelCase								=					dest
      # Backtracking from dest to src
      while self.par[temp] != -1:
        path.append(snake_case				)
        if temp != src:
          for v, w in self.adjList[temp]:
            if v == self.par[temp]:
              cost += w
              break
        __lowerCAmelCase								=					self.par[temp]
      path.append(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: '''      ,    snake_case				)


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







def        __SCREAMING_SNAKE_CASE	(				__lowercase:		int = 10_00):



  '''simple docstring'''






  __lowerCAmelCase								=					0
  for i in range(__lowercase):
    if i % 3 == 0 or i % 5 == 0:
      result += i
  return result


if __name__ == "__main__":
      print(f"""{solution() = }""")
