# coding: utf-8

# # Алгоритм Флойда-Уоршелла

from random import choice
import numpy as np

# ## Список смежности

def adjency_list(edges=None, vertices=None, undirected=False, edges_count=10):
    if edges is None or vertices is None:
        edges = []
        vertices = set()
        for i in range(edges_count):
            v, u = sample(ascii_lowercase, 2)
            edges.append((v, u))
            vertices.add(v)
            vertices.add(u)
        list(vertices)

    adj_list = {v1: set() for v1 in vertices}
    for u, v, w in edges:
        adj_list[u].add((v, w))
        if undirected:
            adj_list[v].add((u, w))
    return adj_list


def input_graph(undirected=False):
    edges_count = int(input('Введите кол-во ребер: '))
    edges = []
    vertices = set()
    for i in range(edges_count):
        u, v, w = list(map(int, input('Введите 2 вершины и вес через пробел: ').split()))
        edges.append((u, v, w))
        vertices.add(u)
        vertices.add(v)
    return adjency_list(edges, list(vertices), undirected=undirected)


def floyd_warshall(adj_list):
    dist = np.full((len(adj_list), len(adj_list)), np.inf)
    for i in adj_list.keys():
        dist[i, i] = 0
        for j, w in adj_list[i]:
            dist[i, j] = w

    for k in range(len(adj_list)):
        for i in range(len(adj_list)):
            for j in range(len(adj_list)):
                dist[i,j] = min(dist[i, j],
                                dist[i, k] + dist[k, j])
    return dist


# ### Демонстрация

def main():
    a = input_graph()
    print(floyd_warshall(a))


if __name__ == '__main__':
    main()