

'''simple docstring'''







from __future__ import annotations

from sys import maxsize
from typing import Generic, TypeVar

__lowerCamelCase						    =     TypeVar('''T''')
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     int:
       return (position - 1) // 2
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     int:
       return (2 * position) + 1
def  UpperCAmelCase__      ( UpperCAmelCase__			)     ->     int:
       return (2 * position) + 2


class    A__ ( Generic[T]     ):



    def __init__(   self    )  -> None:





           '''simple docstring'''
           A_		   = []
           A_		   = {}
           A_		   = 0



    def __len__(   self    )  -> int:





           '''simple docstring'''
           return self.elements



    def __repr__(   self    )  -> str:





           '''simple docstring'''
           return str(self.heap    )



    def    snake_case_     (   self    )  -> bool:





           '''simple docstring'''
           return self.elements == 0



    def    snake_case_     (   self						,			UpperCamelCase__						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           self.heap.append((elem, weight)    )
           A_		   = self.elements
           self.elements += 1
           self._bubble_up(UpperCamelCase__    )



    def    snake_case_     (   self    )  -> T:





           '''simple docstring'''
           # Remove and return the element with lowest weight (highest priority)
           if self.elements > 1:
                  self._swap_nodes(0						,			self.elements - 1    )
           A_   ,     A_		   = self.heap.pop()
           del self.position_map[elem]
           self.elements -= 1
           if self.elements > 0:
                  A_   ,     A_		   = self.heap[0]
                  self._bubble_down(UpperCamelCase__    )
           return elem



    def    snake_case_     (   self						,			UpperCamelCase__						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           A_		   = self.position_map[elem]
           A_		   = (elem, weight)
           if position > 0:
                  A_		   = get_parent_position(UpperCamelCase__    )
                  A_   ,     A_		   = self.heap[parent_position]
                  if parent_weight > weight:
                         self._bubble_up(UpperCamelCase__    )
                  else:
                         self._bubble_down(UpperCamelCase__    )
           else:
                  self._bubble_down(UpperCamelCase__    )



    def    snake_case_     (   self						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           A_		   = self.position_map[elem]
           if curr_pos == 0:
                  return None
           A_		   = get_parent_position(UpperCamelCase__    )
           A_   ,     A_		   = self.heap[curr_pos]
           A_   ,     A_		   = self.heap[parent_position]
           if parent_weight > weight:
                  self._swap_nodes(UpperCamelCase__						,			UpperCamelCase__    )
                  return self._bubble_up(UpperCamelCase__    )
           return None



    def    snake_case_     (   self						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           A_		   = self.position_map[elem]
           A_   ,     A_		   = self.heap[curr_pos]
           A_		   = get_child_left_position(UpperCamelCase__    )
           A_		   = get_child_right_position(UpperCamelCase__    )
           if child_left_position < self.elements and child_right_position < self.elements:
                  A_   ,     A_		   = self.heap[child_left_position]
                  A_   ,     A_		   = self.heap[child_right_position]
                  if child_right_weight < child_left_weight and child_right_weight < weight:
                         self._swap_nodes(UpperCamelCase__						,			UpperCamelCase__    )
                         return self._bubble_down(UpperCamelCase__    )
           if child_left_position < self.elements:
                  A_   ,     A_		   = self.heap[child_left_position]
                  if child_left_weight < weight:
                         self._swap_nodes(UpperCamelCase__						,			UpperCamelCase__    )
                         return self._bubble_down(UpperCamelCase__    )
           else:
                  return None
           if child_right_position < self.elements:
                  A_   ,     A_		   = self.heap[child_right_position]
                  if child_right_weight < weight:
                         self._swap_nodes(UpperCamelCase__						,			UpperCamelCase__    )
                         return self._bubble_down(UpperCamelCase__    )
           return None







    def    snake_case_     (   self						,			UpperCamelCase__						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           A_		   = self.heap[nodea_pos][0]
           A_		   = self.heap[nodea_pos][0]
           A_   ,     A_		   = (
               self.heap[nodea_pos],
               self.heap[nodea_pos],
           )
           A_		   = nodea_pos
           A_		   = nodea_pos


class    A__ ( Generic[T]     ):



    def __init__(   self    )  -> None:





           '''simple docstring'''
           A_		   = {}
           A_		   = 0



    def __repr__(   self    )  -> str:





           '''simple docstring'''
           return str(self.connections    )



    def __len__(   self    )  -> int:





           '''simple docstring'''
           return self.nodes



    def    snake_case_     (   self						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           # Add a node in the graph if it is not in the graph
           if node not in self.connections:
                  A_		   = {}
                  self.nodes += 1







    def    snake_case_     (   self						,			UpperCamelCase__						,			UpperCamelCase__						,			UpperCamelCase__    )  -> None:





           '''simple docstring'''
           self.add_node(UpperCamelCase__    )
           self.add_node(UpperCamelCase__    )
           A_		   = weight
           A_		   = weight

def  UpperCAmelCase__      ( UpperCAmelCase__,    )     ->     tuple[dict[T, int], dict[T, T | None]]:
       A_		   = {node: maxsize for node in graph.connections}
       A_		   = {node: None for node in graph.connections}

       A_		   = MinPriorityQueue()
       for node, weight in dist.items():
              priority_queue.push(UpperCAmelCase__,    UpperCAmelCase__			)

       if priority_queue.is_empty():
              return dist, parent

       # initialization
       A_		   = priority_queue.extract_min()
       A_		   = 0
       for neighbour in graph.connections[node]:
              if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
                     A_		   = dist[node] + graph.connections[node][neighbour]
                     priority_queue.update_key(UpperCAmelCase__,    dist[neighbour]			)
                     A_		   = node

    # running prim's algorithm
       while not priority_queue.is_empty():
              A_		   = priority_queue.extract_min()
              for neighbour in graph.connections[node]:
                     if dist[neighbour] > dist[node] + graph.connections[node][neighbour]:
                            A_		   = dist[node] + graph.connections[node][neighbour]
                            priority_queue.update_key(UpperCAmelCase__,    dist[neighbour]			)
                            A_		   = node
       return dist, parent



'''simple docstring'''







def  UpperCAmelCase__      ( UpperCAmelCase__ = 10_00			)     ->     int:
       return sum(2 * a * ((a - 1) // 2) for a in range(3,    n + 1			)			)


if __name__ == "__main__":
      print(solution())
