#include<bits/stdc++.h>
using namespace std;
int s[105][105],n,m,x,y,v;
bool q[105][105];
int main()
{
	cin >> n >> m;
	memset(s,1,sizeof(s));
//	cout << s[1][1];
	while(m --)
	{
		cin >> x >> y >> v;
		s[x][y] = v;
		q[x][y] = 1;
	}
	for(int i = 1;i <= n;i ++)//就是这里
		for(int j = 1;j <= n;j ++)
		{
			for(int k = 1;k <= n;k ++)
			{
				if(q[i][k] && q[j][k])
					s[i][j] = min(s[i][j],s[i][k] + s[j][k]);
			}
		}
	for(int i = 1;i <= n;i ++)
	{
		for(int j = 1;j <= n;j ++)
		{
			if(s[i][j] != 16843009)
				cout << s[i][j] << ' ';
			else
				cout << 0 << ' ';
		}
		cout << '\n';
	}
	return 0;
}