from __future__ import annotations

import math



def lowerCamelCase  (       SCREAMING_SNAKE_CASE  ,      SCREAMING_SNAKE_CASE     ):
    '''simple docstring'''







    if len(__UpperCamelCase     ) != 2 or len(a[0]     ) != 2 or len(__UpperCamelCase     ) != 2 or len(b[0]     ) != 2:
        raise Exception('''Matrices are not 2x2'''     )
    __UpperCamelCase					:List[str]        =		[
        [a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],
        [a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],
    ]
    return new_matrix



def lowerCamelCase  (       SCREAMING_SNAKE_CASE  ,      SCREAMING_SNAKE_CASE     ):
    '''simple docstring'''







    return [
        [matrix_a[row][col] + matrix_b[row][col] for col in range(len(matrix_a[row]     )     )]
        for row in range(len(__UpperCamelCase     )     )
    ]



def lowerCamelCase  (       SCREAMING_SNAKE_CASE  ,      SCREAMING_SNAKE_CASE     ):
    '''simple docstring'''







    return [
        [matrix_a[row][col] - matrix_b[row][col] for col in range(len(matrix_a[row]     )     )]
        for row in range(len(__UpperCamelCase     )     )
    ]



def lowerCamelCase  (       SCREAMING_SNAKE_CASE     ):
    '''simple docstring'''







    if len(__UpperCamelCase     ) % 2 != 0 or len(a[0]     ) % 2 != 0:
        raise Exception('''Odd matrices are not supported!'''     )

    __UpperCamelCase					:List[str]        =		len(__UpperCamelCase     )
    __UpperCamelCase					:List[str]        =		matrix_length // 2

    __UpperCamelCase					:int        =		[[a[i][j] for j in range(__UpperCamelCase  ,      __UpperCamelCase     )] for i in range(__UpperCamelCase     )]
    __UpperCamelCase					:str        =		[
        [a[i][j] for j in range(__UpperCamelCase  ,      __UpperCamelCase     )] for i in range(__UpperCamelCase  ,      __UpperCamelCase     )
    ]

    __UpperCamelCase					:Optional[Any]        =		[[a[i][j] for j in range(__UpperCamelCase     )] for i in range(__UpperCamelCase     )]
    __UpperCamelCase					:List[str]        =		[[a[i][j] for j in range(__UpperCamelCase     )] for i in range(__UpperCamelCase  ,      __UpperCamelCase     )]

    return top_left, top_right, bot_left, bot_right



def lowerCamelCase  (       SCREAMING_SNAKE_CASE     ):
    '''simple docstring'''







    return len(__UpperCamelCase     ), len(matrix[0]     )



def lowerCamelCase  (       SCREAMING_SNAKE_CASE     ):
    '''simple docstring'''







    print('''\n'''.join(str(__UpperCamelCase     ) for line in matrix     )     )



def lowerCamelCase  (       SCREAMING_SNAKE_CASE  ,      SCREAMING_SNAKE_CASE     ):
    '''simple docstring'''







    if matrix_dimensions(__UpperCamelCase     ) == (2, 2):
        return default_matrix_multiplication(__UpperCamelCase  ,      __UpperCamelCase     )

    __UpperCamelCase  ,	__UpperCamelCase  ,	__UpperCamelCase  ,	__UpperCamelCase					:int        =		split_matrix(__UpperCamelCase     )
    __UpperCamelCase  ,	__UpperCamelCase  ,	__UpperCamelCase  ,	__UpperCamelCase					:Optional[int]        =		split_matrix(__UpperCamelCase     )

    __UpperCamelCase					:int        =		actual_strassen(__UpperCamelCase  ,      matrix_subtraction(__UpperCamelCase  ,      __UpperCamelCase     )     )
    __UpperCamelCase					:Optional[Any]        =		actual_strassen(matrix_addition(__UpperCamelCase  ,      __UpperCamelCase     )  ,      __UpperCamelCase     )
    __UpperCamelCase					:List[str]        =		actual_strassen(matrix_addition(__UpperCamelCase  ,      __UpperCamelCase     )  ,      __UpperCamelCase     )
    __UpperCamelCase					:Optional[Any]        =		actual_strassen(__UpperCamelCase  ,      matrix_subtraction(__UpperCamelCase  ,      __UpperCamelCase     )     )
    __UpperCamelCase					:Optional[int]        =		actual_strassen(matrix_addition(__UpperCamelCase  ,      __UpperCamelCase     )  ,      matrix_addition(__UpperCamelCase  ,      __UpperCamelCase     )     )
    __UpperCamelCase					:Any        =		actual_strassen(matrix_subtraction(__UpperCamelCase  ,      __UpperCamelCase     )  ,      matrix_addition(__UpperCamelCase  ,      __UpperCamelCase     )     )
    __UpperCamelCase					:Any        =		actual_strassen(matrix_subtraction(__UpperCamelCase  ,      __UpperCamelCase     )  ,      matrix_addition(__UpperCamelCase  ,      __UpperCamelCase     )     )

    __UpperCamelCase					:Optional[Any]        =		matrix_addition(matrix_subtraction(matrix_addition(__UpperCamelCase  ,      __UpperCamelCase     )  ,      __UpperCamelCase     )  ,      __UpperCamelCase     )
    __UpperCamelCase					:Optional[Any]        =		matrix_addition(__UpperCamelCase  ,      __UpperCamelCase     )
    __UpperCamelCase					:Dict        =		matrix_addition(__UpperCamelCase  ,      __UpperCamelCase     )
    __UpperCamelCase					:Optional[int]        =		matrix_subtraction(matrix_subtraction(matrix_addition(__UpperCamelCase  ,      __UpperCamelCase     )  ,      __UpperCamelCase     )  ,      __UpperCamelCase     )

    # construct the new matrix from our 4 quadrants
    __UpperCamelCase					:Any        =		[]
    for i in range(len(__UpperCamelCase     )     ):
        new_matrix.append(top_left[i] + top_right[i]     )
    for i in range(len(__UpperCamelCase     )     ):
        new_matrix.append(bot_left[i] + bot_right[i]     )
    return new_matrix



def lowerCamelCase  (       SCREAMING_SNAKE_CASE  ,      SCREAMING_SNAKE_CASE     ):
    '''simple docstring'''







    if matrix_dimensions(__UpperCamelCase     )[1] != matrix_dimensions(__UpperCamelCase     )[0]:
        __UpperCamelCase					:int        =		(
            '''Unable to multiply these matrices, please check the dimensions.\n'''
            f"""Matrix A: {matrixa}\n"""
            f"""Matrix B: {matrixa}"""
        )
        raise Exception(__UpperCamelCase     )
    __UpperCamelCase					:int        =		matrix_dimensions(__UpperCamelCase     )
    __UpperCamelCase					:Tuple        =		matrix_dimensions(__UpperCamelCase     )

    if dimensiona[0] == dimensiona[1] and dimensiona[0] == dimensiona[1]:
        return [matrixa, matrixa]

    __UpperCamelCase					:Optional[Any]        =		max(*__UpperCamelCase  ,      *__UpperCamelCase     )
    __UpperCamelCase					:Optional[Any]        =		int(math.pow(2  ,      math.ceil(math.loga(__UpperCamelCase     )     )     )     )
    __UpperCamelCase					:List[Any]        =		matrixa
    __UpperCamelCase					:List[str]        =		matrixa

    # Adding zeros to the matrices so that the arrays dimensions are the same and also
    # power of 2
    for i in range(0  ,      __UpperCamelCase     ):
        if i < dimensiona[0]:
            for _ in range(dimensiona[1]  ,      __UpperCamelCase     ):
                new_matrixa[i].append(0     )
        else:
            new_matrixa.append([0] * maxim     )
        if i < dimensiona[0]:
            for _ in range(dimensiona[1]  ,      __UpperCamelCase     ):
                new_matrixa[i].append(0     )
        else:
            new_matrixa.append([0] * maxim     )

    __UpperCamelCase					:List[str]        =		actual_strassen(__UpperCamelCase  ,      __UpperCamelCase     )

    # Removing the additional zeros
    for i in range(0  ,      __UpperCamelCase     ):
        if i < dimensiona[0]:
            for _ in range(dimensiona[1]  ,      __UpperCamelCase     ):
                final_matrix[i].pop()
        else:
            final_matrix.pop()
    return final_matrix


if __name__ == "__main__":
    __lowercase										= [
        [2, 3, 4, 5],
        [6, 4, 3, 1],
        [2, 3, 6, 7],
        [3, 1, 2, 4],
        [2, 3, 4, 5],
        [6, 4, 3, 1],
        [2, 3, 6, 7],
        [3, 1, 2, 4],
        [2, 3, 4, 5],
        [6, 2, 3, 1],
    ]
    __lowercase										= [[0, 2, 1, 1], [16, 2, 3, 3], [2, 2, 7, 7], [13, 11, 22, 4]]
    print(strassen(matrixa, matrixa))






from __future__ import annotations



def lowerCamelCase  (       SCREAMING_SNAKE_CASE  ,      SCREAMING_SNAKE_CASE     ):
    '''simple docstring'''







    print(f"""Vertex\tShortest Distance from vertex {src}"""     )
    for i, d in enumerate(SCREAMING_SNAKE_CASE     ):
        print(f"""{i}\t\t{d}"""     )



def lowerCamelCase  (       SCREAMING_SNAKE_CASE  ,      SCREAMING_SNAKE_CASE  ,      SCREAMING_SNAKE_CASE     ):
    '''simple docstring'''







    for j in range(SCREAMING_SNAKE_CASE     ):
        __UpperCamelCase  ,	__UpperCamelCase  ,	__UpperCamelCase					:int        =		(graph[j][k] for k in ['''src''', '''dst''', '''weight'''])
        if distance[u] != float('''inf'''     ) and distance[u] + w < distance[v]:
            return True
    return False



def lowerCamelCase  (       SCREAMING_SNAKE_CASE  ,      SCREAMING_SNAKE_CASE  ,      SCREAMING_SNAKE_CASE  ,      SCREAMING_SNAKE_CASE     ):
    '''simple docstring'''







    __UpperCamelCase					:List[Any]        =		[float('''inf'''     )] * vertex_count
    __UpperCamelCase					:str        =		0.0

    for _ in range(vertex_count - 1     ):
        for j in range(SCREAMING_SNAKE_CASE     ):
            __UpperCamelCase  ,	__UpperCamelCase  ,	__UpperCamelCase					:Dict        =		(graph[j][k] for k in ['''src''', '''dst''', '''weight'''])

            if distance[u] != float('''inf'''     ) and distance[u] + w < distance[v]:
                __UpperCamelCase					:Any        =		distance[u] + w

    __UpperCamelCase					:Tuple        =		check_negative_cycle(SCREAMING_SNAKE_CASE  ,      SCREAMING_SNAKE_CASE  ,      SCREAMING_SNAKE_CASE     )
    if negative_cycle_exists:
        raise Exception('''Negative cycle found'''     )

    return distance


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    __lowercase										= int(input('''Enter number of vertices: ''').strip())
    __lowercase										= int(input('''Enter number of edges: ''').strip())

    __lowercase										= [{} for _ in range(E)]

    for i in range(E):
        print('''Edge ''', i + 1)
        __lowercase			,	__lowercase			,	__lowercase										= (
            int(x)
            for x in input('''Enter source, destination, weight: ''').strip().split(''' ''')
        )
        __lowercase										= {'''src''': src, '''dst''': dest, '''weight''': weight}

    __lowercase										= int(input('''\nEnter shortest path source:''').strip())
    __lowercase										= bellman_ford(graph, V, E, source)
    print_distance(shortest_distance, 0)





