1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

import sys

 

input = sys.stdin.readline

V = int(input())

E = int(input())

 

INF = 1e9

graph = [[INF] * (V + 1) for _ in range(V + 1)]

distance = [INF] * (V + 1)

 

for _ in range(E):

    u, v, w = map(int, input().split())

    graph[u][v] = min(graph[u][v], w)

 

for i in range(1, V + 1):

    graph[i][i] = 0

 

for i in range(1, V + 1):

    for j in range(1, V + 1):

        for k in range(1, V + 1):

            graph[j][k] = min(graph[j][k], graph[j][i] + graph[i][k])

 

for i in range(1, V + 1):

    for j in range(1, V + 1):

        if graph[i][j] == INF:

            print(‘0’, end=‘ ‘)

            continue

        print(graph[i][j], end=‘ ‘)

    print()