

import heapq


def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						Union[str, Any]	,				_SCREAMING_SNAKE_CASE   :						List[str]	,				_SCREAMING_SNAKE_CASE   :						List[str]    ):





    """simple docstring"""


    SCREAMING_SNAKE_CASE_													=  [(0, start)]  # cost from start node,end node
    SCREAMING_SNAKE_CASE_													=  set()
    while heap:
        ((SCREAMING_SNAKE_CASE_)							,     (SCREAMING_SNAKE_CASE_))													=  heapq.heappop(_SCREAMING_SNAKE_CASE    )
        if u in visited:
            continue
        visited.add(_SCREAMING_SNAKE_CASE    )
        if u == end:
            return cost
        for v, c in graph[u]:
            if v in visited:
                continue
            SCREAMING_SNAKE_CASE_													=  cost + c
            heapq.heappush(_SCREAMING_SNAKE_CASE	,				(next_item, v)    )
    return -1


UpperCamelCase__					: Any								=      {
    "A": [["B", 2], ["C", 5]],
    "B": [["A", 2], ["D", 3], ["E", 1], ["F", 1]],
    "C": [["A", 5], ["F", 3]],
    "D": [["B", 3]],
    "E": [["B", 4], ["F", 3]],
    "F": [["C", 3], ["E", 3]],
}
UpperCamelCase__					: List[str]								=      {
    "B": [["C", 1]],
    "C": [["D", 1]],
    "D": [["F", 1]],
    "E": [["B", 1], ["F", 3]],
    "F": [],
}
UpperCamelCase__					: List[Any]								=      {
    "B": [["C", 1]],
    "C": [["D", 1]],
    "D": [["F", 1]],
    "E": [["B", 1], ["G", 2]],
    "F": [],
    "G": [["F", 1]],
}

UpperCamelCase__					: Union[str, Any]								=      dijkstra(G, "E", "C")
print(short_distance)  # E -- 3 --> F -- 3 --> C == 6

UpperCamelCase__					: List[str]								=      dijkstra(Ga, "E", "F")
print(short_distance)  # E -- 3 --> F == 3

UpperCamelCase__					: int								=      dijkstra(Ga, "E", "F")
print(short_distance)  # E -- 2 --> G -- 1 --> F == 3

if __name__ == "__main__":
       import doctest

       doctest.testmod()





def    _UpperCAmelCase    (					_SCREAMING_SNAKE_CASE   :						int	,				_SCREAMING_SNAKE_CASE   :						int	,				_SCREAMING_SNAKE_CASE   :						int    ):





    """simple docstring"""


    if power < 0:
        return -1
    base %= mod
    SCREAMING_SNAKE_CASE_													=  1

    while power > 0:
        if power & 1:
            SCREAMING_SNAKE_CASE_													=  (result * base) % mod
        SCREAMING_SNAKE_CASE_													=  power >> 1
        SCREAMING_SNAKE_CASE_													=  (base * base) % mod

    return result


def    _UpperCAmelCase    (					):





    """simple docstring"""


    print(modular_exponential(3	,				200	,				13    )    )


if __name__ == "__main__":
       import doctest

       doctest.testmod()

       main()


