FLOYD WHARSHALL

INF = 999

def all_sources_shortest_path(graph):
    num_vertices = len(graph)

    # Initialize the distance matrix with the graph's adjacency matrix
    distance = [list(row) for row in graph]

    # Floyd-Warshall algorithm
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

    return distance

def print_matrix(matrix):
    for row in matrix:
        for value in row:
            if value == INF:
                print("INF", end="::")
            else:
                print(value, end="::")
        print()

def main():
    num_vertices = int(input())
    
    # Initialize the graph with INF for unconnected edges
    graph = [[INF] * num_vertices for _ in range(num_vertices)]

    # Take input for the edge weights
    for i in range(num_vertices):
        for j in range(num_vertices):
            weight = int(input())
            graph[i][j] = weight

    # Display the directed graph
    print_matrix(graph)
    print(" ")
    print("*** ")
    # Calculate and display the all sources shortest path
    result = all_sources_shortest_path(graph)
    print_matrix(result)

if _name_ == "_main_":
    main()