# 무한 상정
INF = int(1e9)

# 노드의 개수 및 간선의 개수를 입력 받기
n = int(input())
m = int(input())
# 2차원 그래프 리스트 만들기 및 무한 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신으로 가는 경우를 0으로 초기화
for a in range(1, n + 1):
	for b in range(1, n + 1):
		if a == b:
			graph[a][b] = 0

# 각 간선의 정보를 입력 받기
for _ in range(m):
	# a노드에서 b노드로 가는데 걸리는 비용 c
	a, b, c = map(int, input().split())
	graph[a][b] = c

# 점화식에 따른 플로이드 워셜 알고리즘 사용
for k in range(1, n + 1):
	for a in range(1, n + 1):
		for b in range(1, n + 1):
			graph[a][b] = min(graph[a][b], graph[a][k] + graph[b][k])

# 출력 
for a in range(1, n + 1):
	for b in range(1, n + 1):
		if graph[a][b] == INF:
			print("INFINITY", end = " ")
		else :
			print(graph[a][b], end = " ")
	print()

#include <bits/stdc++.h>
#define INF 1e9

using namespace std;

int n, m
int graph[501][501];
// 해당 유형의 시간수행 복잡도를 생각할 때,
// 해당 유형 문제는 노드 개수가 500개 이상으로 구현하기 어렵습니다. 

int main(void)
{
	cin >> n >> m
	for (int i = 0; i < 501; i++)
		fill(graph[i], graph[i] + 501, INF);
	
	for (int a = 1; a <= n; a++)
		for (int b = 1; b <= n; b++)
			if (a == b)
				graph[a][b] = 0;

	for (int i = 0; i < m; i++)
		int a, b, c;
		cin >> a >> b >> c;
		graph[a][b] = c;

	for (int k = 1; k <= n; k++)
		for (int a = 1; a <= n; a++)
			for (int b = 1; b <= n; b++)
				graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b]);

	for (int a = 1; a <= n; a++)
	{	
		for (int b = 1; b <= n; b++)
		{
			if (graph[a][b] == INF)
				cout >> "INFINITY" >> ' ';
			else
				cout >> graph[a][b] >> ' ';
		}
		cout >> '\n';
	}
}