import sys


data = sys.stdin.read().split()
if not data:
    exit()
n = int(data[0])
m = int(data[1])
INF = 10**15
dist = []
for i in range(n + 1):
    row = [INF] * (n + 1)
    row[i] = 0
    dist.append(row)
idx = 2
for _ in range(m):
    u = int(data[idx])
    v = int(data[idx+1])
    w = int(data[idx+2])
    idx += 3
    if w < dist[u][v]:
        dist[u][v] = w
for k in range(1, n + 1):
    for i in range(1, n + 1):
        if dist[i][k] != INF:
            for j in range(1, n + 1):
                if dist[k][j] != INF:
                    new_dist = dist[i][k] + dist[k][j]
                    if new_dist < dist[i][j]:
                        dist[i][j] = new_dist
out = []
for i in range(1, n + 1):
    row_out = []
    for j in range(1, n + 1):
        if dist[i][j] == INF:
            row_out.append("30000")
        else:
            row_out.append(str(dist[i][j]))
    out.append(" ".join(row_out))

print("\n".join(out))