#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int I=1e9;
int n,m;
int f[2010][2010];
int sta[2010],t;
int d[2010];
void ad(int &x,int y){if(x>y)x=y;}
void wrt(int x){
	if(x<10){putchar('0'+x);return;}
	wrt(x/10),putchar('0'+(x%10));
}
bool vis[2010];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j)f[i][j]=I;
    for(int i=1,u,v,w;i<=m;i++)scanf("%d%d%d",&u,&v,&w),f[u][v]=w;
    for(int i=1;i<=n;i++){
        t=0;
        for(int j=1;j<=n;j++)d[j]=f[i][j];
        memset(vis,0,sizeof(vis));
        for(int j=1;j<=n;j++)if(d[j]<I)vis[j]=1,sta[++t]=j;
        for(int j=1;j<=n;j++){
            for(int k=1;k<=t;k++)ad(d[j],d[sta[k]]+f[sta[k]][j]);
            if(!vis[j]&&d[j]<I)sta[++t]=j,vis[j]=1;
            if(d[j]==I)putchar('-'),putchar('1');
            else wrt(d[j]);
            putchar((j==n)?'\n':' ');
        }
		for(int j=1;j<=n;j++)f[i][j]=d[j];
    }
    return 0;
}