#include<iostream>
#include<cstdio>
#include<queue>
#define N 3000
using namespace std;
const int inf=(int)(1e9);
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
struct reads
{
	int num,data;
	bool operator < (const reads &t)const
	{
		return data>t.data;	
	}
};
int n,m,X[N+1],Y[N+1],Z[N+1],dp[N+1],ans[N+1][N+1],dis[N+1];
bool used[N+1],vis[N+1],vst[N+1][N+1];
vector<reads>E[N+1];
void solve(int op)
{
	priority_queue<reads>q;
	int top;
	for (int i=1;i<=n;++i) E[i].clear();
	for (int i=1;i<=m;++i)
		if (vis[i])
			E[X[i]].push_back((reads){Y[i],Z[i]});
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<=n;++j) dis[j]=inf,used[j]=0;
		dis[i]=0,q.push((reads){i,0});
		while (!q.empty())
		{
			top=q.top().num,q.pop();
			if (used[top]) continue;
			used[top]=1;
			for (int j=0;j<E[top].size();++j)
				if ((top<=i||E[top][j].num<=i)&&dis[E[top][j].num]>dis[top]+E[top][j].data)
					dis[E[top][j].num]=dis[top]+E[top][j].data,q.push((reads){E[top][j].num,dis[E[top][j].num]});
		}
		for (int j=i+1;j<=n;++j) dp[j]=inf;
		for (int j=1;j<=n;++j)
			for (int t=0;t<E[j].size();++t)
				if (E[j][t].num>i)
					dp[E[j][t].num]=min(dp[E[j][t].num],dis[j]+E[j][t].data);
		for (int j=i+1;j<=n;++j)
			for (int t=0;t<E[j].size();++t)
				if (j<E[j][t].num)
					dp[E[j][t].num]=min(dp[E[j][t].num],dp[j]+E[j][t].data);
		for (int j=i+1;j<=n;++j)
		{
			if (!op) ans[i][j]=dp[j];
			else ans[j][i]=dp[j];
		}
	}
	return;
}
int main()
{
	n=read(),m=read();
	for (int i=1;i<=m;++i) X[i]=read(),Y[i]=read(),Z[i]=read();
	for (int i=m;i>=1;--i)
	{
		if (!vst[X[i]][Y[i]]) vis[i]=1;
		vst[X[i]][Y[i]]=1;
	}
	solve(0);
	for (int i=1;i<=m;++i) swap(X[i],Y[i]);
	solve(1);
	for (int i=1;i<=n;++i)
	{
		for (int j=1;j<=n;++j) printf("%d ",ans[i][j]==inf?-1:ans[i][j]);
		puts("");
	}
	return 0;
}