3 3
1 2 3
2 3 1
1 3 7

0 3 4
3 0 1
4 1 0

INF = float('inf')
n, m = map(int, input().split())
dp = [[INF]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    dp[i][i] = 0
for _ in range(m):
    u, v, w = map(int, input().split())
    dp[u][v] = min(dp[u][v], w)
    dp[v][u] = min(dp[v][u], w)
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j])
for i in range(1, n+1):
    row = [str(dp[i][j]) if dp[i][j] != INF else 'INF' for j in range(1, n+1)]
    print(' '.join(row))