#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int N = 610;
#define LL long long
int n,m;
LL st[N][N],b[N][N],dis[N];
bool vis[N];
inline LL read(){
    LL x=0,f=1;
    char ch;
    while((ch=getchar())<'0'||ch>'9')if(ch=='-')f=-1;
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
int main(){
    int i,j,n,m;
    n=read(),m=read();
    memset(st,0x3f,sizeof st);
    for(i=0;i<m;i++){
        LL cn1,cn2,cn3;
        cn1=read(),cn2=read(),cn3=read();
        st[cn1][cn2]=min(st[cn1][cn2],cn3);
    }
    for(i=0;i<n;i++){
        for(j=0;j<2*n;j++){
            int x=j%n;
            int nex=(x+1)%n;
            st[i][nex]=min(st[i][nex],st[i][x]+1);
        }
    }
    for(i=0;i<n;i++){
        memset(dis,0x3f,sizeof dis);
        memset(vis,false,sizeof vis);
        dis[i]=0;
        while(1){
            int mark=-1;
            LL min1=0x3f3f3f3f;
            for(int k=0;k<n;k++){
                if(!vis[k]&&(mark==-1||dis[k]<min1)){
                    mark=k;
                    min1=dis[k];
                }
            }
            if(mark==-1)break;
            vis[mark]=true;
            for(int k=0;k<n;k++){
                dis[(k+dis[mark])%n]=min(dis[(k+dis[mark])%n],st[mark][k]+dis[mark]);
            }
        }
        dis[i]=0;
        for(j=0;j<n;j++)cout<<dis[j]<<" ";cout<<endl;
    }
    return 0;
}