#include<cstdio>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;

// #define NDEBUG
#include<cassert>

#define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
#define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
#define fi first
#define se second
#define mp(a, b) make_pair(a, b)
#define Endl putchar('\n')
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T>inline T fab(T x){ return x<0? -x: x; }
template<class T>inline T readin(T x){
    x=0; int f=0; char c;
    while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
    for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
    return f? -x: x;
}
template<class T>inline void writc(T x, char s='\n'){
    static int fwri_sta[1005], fwri_ed=0;
    if(x<0) putchar('-'), x=-x;
    do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
    while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
    putchar(s);
}

const int maxn=600;
const ll inf=1ll<<60;

ll tp[maxn+5][maxn+5], n, m;

inline int get(int x){ return (x%n+n)%n; }

inline void input(){
    n=readin(1), m=readin(1);
    memset(tp, 0x3f, sizeof tp);
    int u, v, w;
    rep(i, 1, m){
        u=readin(1), v=readin(1), w=readin(1);
        tp[u][v]=w;
    }
}

inline void gettp(){
    rep(i, 0, n-1){
        rep(j, 1, n-1) tp[i][j]=min(tp[i][j], tp[i][j-1]+1);
        tp[i][0]=min(tp[i][0], tp[i][get(-1)]+1);
        rep(j, 1, n-1) tp[i][j]=min(tp[i][j], tp[i][j-1]+1);
        tp[i][0]=min(tp[i][0], tp[i][get(-1)]+1);
    }
}

ll f[maxn+5][maxn+5];
int vis[maxn+5];
inline void getf(){
    memset(f, 0x3f, sizeof f);
    rep(s, 0, n-1){
        f[s][s]=0, f[s][n]=inf;
        memset(vis, 0, sizeof vis);
        for(int t=0; t<n; ++t){
            pair<long long, int> elem=mp(inf, n);
            rep(i, 0, n-1) if(!vis[i])
                elem=min(elem, mp(f[s][i], i));
            if(elem.se==n) break;
            int u=elem.se, cur=elem.fi, to;
            vis[u]=1;
            rep(i, 0, n-1){
                to=get(i-cur);
                if(cur+tp[u][to]<f[s][i])
                    f[s][i]=cur+tp[u][to];
            }
        }
    }
}

signed main(){
    input();
    gettp();
    getf();
    rep(i, 0, n-1){
        rep(j, 0, n-1) writc(f[i][j], ' ');
        Endl;
    }
    return 0;
}